Students in Fudan University have various extracurricular lives. It seems to be widely known that many students in the Zhangjiang Campus prefer Tractor (a game of poker with four players, also named as ‘80-points’ or ‘Upgrading’), but it is true that a considerable mass of students (especially in Department of Computer S&T) love another four player game, Mahjong, very much. Mahjong is one of the most historied multiplayer games in China. People in several provinces prefer this game most with various modified rules respectively. To begin this problem, firstly, we shall introduce some basic concepts about the game: • Game Going The game of Mahjong is played with a special set of ‘Mahjong Tiles’, which made by piece of wood or stones, each tile have a corresponding image on one face, which denotes particular signification. Initially, all tiles should be randomly shuffled and put into a pile with their (tiles’) faces down, thus all their contents are hidden. After that, the participating players each get 13 tiles as there Holding Tiles (will be definitely explained and discussed later). Consequently, players come to the ”Dealing Section” that everyone alternatively gets one tile from the hidden pile and includes it into this player’s Holding Tiles, then chooses one tile from the current Holding Tiles to discard. This procedure will continue until there’s no tile in the hidden pile or any player meet the Win condition (Practically, there are further modified rules such as ”Bloody Battle”, which pronounced as ”Shyue-Chan” in Chinese, will break this traditional rule, but we do not take them into account in this problem). • Holding Tiles In the process of game, players should manage their own set of tiles; these tiles are considered as Holding Tiles of each player respectively. Holding Tiles of one player have two particular types: Declared and Hidden. Declared Tiles are shown into public while Hidden Tiles are kept private, thus one can know all the four players’ Declared Tiles but only his or her own Hidden Tiles. The event causing Hidden Tiles into Declared will be discussed later. • Win Before introducing the concept of how to Win a game, we have to firstly give out two essential sub-concepts, please remember that they are quite important for solving this problem: (a) Architecture A player’s Holding Tiles are just a set of tiles, they can be separated and assembled into special Components, and all these Components compose the Architecture of Holding Tiles. (b) Analysis The procedure and method to determine the Architecture of one’s Holding Tiles is called Analysis (please ignore the changing part of speech). Analyzing one’s Holding Tiles should be based on a system of related rules and might be somewhat complex and tricky, discussed later. In the rules of Mahjong, the Target Architecture will be defined. As the name implies, if a player’s Holding Tiles can be Analyzed into a particular Architecture coinciding the Target Architecture, then this player can Win the game.
2/8 • Score After one player Win a game, the score of this Win should be judged under a scoring rules system. The score is used for determining the worth of this Win — It is widely known that Mahjong is originally invited for gambling. Description Now in China, people in Sichuan Province prefer the game of Mahjong much more than people in other area; causally, most of students in Fudan University who prefer Mahjong come from Sichuan. To this reason, we would like to use the rule of Sichuan Mahjong to go on this problem. With related to the traditional Mahjong rule, regulation of this game in Sichuan Province have been changed most obviously in the following two ways: • Tiles simplification In the original rule of Chinese Mahjong, the game is based on a large set of tiles. All these tiles can be classified into several Categories — including Simple Category, Honor Category, and Bonus Category — with different functions when the game playing. The last two kinds of Categories are used in rules of some other area of China. (In other words, has nothing to do with this problem) Sichuan Mahjong only uses Simple Category in the game: There are three different Suits in Simple Category and each Suit is numbered 1 to 9. They are Dots, Bamboo and Myriads. Dots numbered 1 to 9. Myriads numbered 1 to 9. Bamboo numbered 1 to 9. There are four matching tiles for each value (e.g. there are four Dots tiles with the number 2). Generally, there are two essential aspects of information for determining the Kind of a tile: the Suit and number, thus we can uniquely name a tile with its order of number and Suit, for example: name as ‘Third Bamboo’ and name as ‘First Dots’. Uniquely, players always call (First Bamboo) as ‘Yao-Jhee’. It is easy to calculate that there in total 108 tiles used in the game of Sichuan Mahjong, that is, there are nine kinds in each suit and four tiles of each Kind.
3/8 • Two Suits Limitation This limitation constrains that at most two suits are permitted in one’s Holding Tiles, that is, one with all the three suits in the Holding Tiles can never Win a game (Actually, would cause some penalty). After clarifying these modifications, we can go on the description of Mahjong game. During the process that every player gets new tiles alternatively, there are some situations which would cause case of Interruption. In detail, the rule of Mahjong allows players to meld (‘meld’ is a conventional glossary in Mahjong game, it is better to understand it as ‘adopt’) tiles discarded by others and, after that, sometimes discard a Holding Tiles for exchange. In order to explain the concept of Interruption and the way to Win the game, we shall now define some concepts of components (we’ve mentioned before but never defined) of Holding Tiles. Please review the concept of Target Architecture, a Target Architecture is composed by a set of Components, and there are two kinds of Components: • Sentence There are two kinds of sentences: (a) Sequence A Sequence is a triple of tiles with sequential number, for example: and There must be no skipping of numbers, nor does 9 loop around to 1. The sequence must be in the same Suit. (b) Chunk A Chunk is a triple of tiles with identical number, for example: and There Chunk must be in the same suit. • Pair Similar to Chunk, A Pair is a couple of (two) tiles with identical number and same suit, see the following example: and With the definition of Component, there are three ways of melding others’ discarded tiles, and each time if a player calls for a melding, then an Interruption was made. However, only two ways of Interruption are used in rule of Sichuan Mahjong: • Refine (pronounced as ‘Pong’ in Chinese) If someone discards a tile while you have a Pair of the same tile in your Hidden Tiles, you may (but not must) Refine the discarded tiles with the pair in your hand, after that these three identical tiles should become Declared. As we have mentioned before, each time you Refine a tile, you should discard another Hidden Tile for exchange.
4/8 • Upgrade (pronounced as ‘Kong’ in Chinese) If you have got a sentence of Chunk in Hidden Tiles while another player discards the identical (in fact, the only one) tile — or you get this only identical tile by yourself — you may (but not must) Upgrade the Chunk into a Component with four same tiles (a ‘Kong’) by melding the discarded tile. The same with Refining, after Upgrading these four identical tiles should become Declared. Specially, when making an Upgrade, you should never discard another Hidden Tiles. It seems that after an Upgrade, an extra tile is merged into one’s Holding Tiles (Accurately, into Hidden Tiles), in fact these four same tiles should also be considered as a Chunk, the extra tile is only for ‘honor’, which means being used for calculate the score but never used when Analyzing the Architecture. According to the descriptions of Refine & Upgrade, we can consequently conclude that: • Declared Tiles of a player always come from one or more melding Interruptions. • Once a tile becomes Declared, it will never be back to Hidden and never be discarded any more. Another type of Interruption is Win — Which has been defined above — that is, once another player discards a particular tile, or you get such a tile by yourself, if you can merge such a tile into your Holding Tiles and then Analyze all the Holding Tiles (14 tiles now) as a Target Architecture, then you can Win this game. Now, we should give the detailed explanation of Target Architecture under the rule of Sichuan Mahjong. The Target Architecture of Holding Tiles can be considered as that: • Following the Two Suits Limitation. • Components in the Architecture fits one of the following two structural styles: (a) Consist of FOUR Sentences and ONE Pair, here we name the unique Pair as ‘Jong’. We name this style as Regular Target. (b) Consist of SEVEN Pairs. Remember that the Declared Tiles is a group of Sentences (an Upgraded Chunk can be considered as an ordinary Chunk with ‘honor’ for scoring, discussed later). When Analyzing the Holding Tiles, the Declared Tiles and Hidden Tiles must be considered separately and can never be mixed; furthermore, Declared Tiles can only be Analyzed as several Chunks (ordinary Chunk or Upgraded Chunk) but never Sequences. To finish a Target Architecture, we need 14 tiles, (ignored extra tile from Upgrading), however, each one has only 13 Holding Tiles. Therefore, players always need another extra tile to complete the Architecture; this situation gives the concept of Expected Tile: If a player’s Holding Tiles can fit the Target Architecture by adding a particular and existing tile, then such a tile is considered as one of the player’s Expecting Tiles. Pay attention on the word ‘existing’ please: that is, if you have held all such existing (four) tiles, then this kind of tile cannot be considered as Expected Tile. Now we come to specify the rule of Scoring: once a player meets the Target Architecture (has got Win), he or she will have the basic score of ONE, that is, the lowest score of a Win is ONE. In addition, there are lots of specific conditions for awarding further extra scores. See the following items for description: • Dragon (pronounced as ‘Kong’ and ‘Gher’ in Chinese, especially in Chengdu dialect) If a player has collected all the four tiles of same kind of tiles in his or her Holding Tiles, then we say this kind become a Dragon. Each Dragon gives the owner ONE additional score.
5/8 Apparently, once a player making an Interruption of Upgrade, a Declared Dragon is created, but there’s another situation: sometimes player shows a Declared Chunk in Declared Tiles but hides the rest one of that kind of tiles in Hidden Tiles, or even hides all the four same tiles in Hidden Tiles, these two cases will also be acknowledged as Dragon. • Seven Couples (pronounced as ”Chee Dwee” in Chinese) If the Architecture meets the second style of Target Architecture — in other words: consists by seven pairs — then such an Architecture can be identified as Seven Couples, this special style gives the owner TWO additional score. • Purely (pronounced as ”Ching Yi-Seh” in Chinese) If one players all Holding Tiles (Attention, not only the Hidden or Declared Tiles) have the same Suit, then Purely can be identified, TWO additional score awarded. • Chunkious (pronounced as ”Dwee-Tsi Hoo” in Chinese) Chunkious is a special style of Regular Target, the condition is that all sentences of Holding Tiles are Chunks, Sequence never appears. Chunkious is worth ONE additional score. • Sky-ground Related (pronounced as ”Tai Yao-Jhew” in Chinese) This is a very unique and confusing rule in Sichuan Mahjong, even not all players in Sichuan admit this condition, but in this problem we take it into account for generalization. No matter what style of Target Architectures, the condition of Sky-ground Related asks each components in the Architecture have at least one tile has numbers of 1 or 9. For instance, the following components are acceptable: This special style gives the owner TWO additional scores. • Royal Chunkious (pronounced as ”Jong Dwee” in Chinese) As the name implies, the Royal Chunkious is a special style of Chunkious, thus if an Archi- tecture does not meet the condition of Chunkious, it can never be judged as Royal. This style means in an Architecture of Chunkious, only tiles with numbers 2, 5 and 8 appear. As examples, the following components are valid: Royal Chunkious worth TWO more scores than normal Chunkious. • There are some other items relating to Scoring such as Seizing (‘Chiang Kong’), Lucky Flower (‘Kong Hsiang-Hwa’), but are not considered in this problem. In order to solve this problem, the concept of CONSISTENCE might be somewhat a critical logic. We’ve just listed all the special situation causing extra scores for the Winning player, you may come up with the idea that some of them can occur simultaneously, for example, the following Holding Tiles (has Won): Hidden Tiles are:
6/8 and Declared Tiles are: and This set of Holding Tiles can be obviously Analyzed as an Architecture which meeting the condition of Chunkious, Purely and double Dragons (just Analyze as how they are displayed in the example), and worth 1(basic) + 1(Chunkious) + 2(Purely) + 1(Dragon)*2 = 6 scores. However, when we consider another example: Hidden Tiles are (there is no Declared Tiles in this example): At first glance, we can Analyze them as an Architecture fitting rule of Seven Couples, which is trivial; yet we can also Analyze them in another way (fitting the rule of Sky-ground Related): This way, can we judge the score as 1(basic) + 2(Seven Couples) + 2(Sky-ground Related) = 5? The answer is negative. For explaining this paradox, please remind yourself to notice the definition of Win: a player gets Win means he or she can Analyze the Holding Tiles into a Target Architecture, when we calculate the score, we are in fact aiming at such an resulting Architecture, scilicet, scoring is based on a particular Architecture but not based on the set of Holding Tiles, that is, if a set of Holding Tiles can be Analyzed as more than one Target Architectures, they are independent when scoring and cannot merge. Now we can give the correct answer of the last example: if Analyze in first way, then 1(basic) + 2(Seven Couples) = 3; otherwise, if use the second way, then 1(basic) + 2(Sky-ground Related) = 3, therefore the final score should be considered as 3. The last remaining confusion of scoring is that: if two or more Analyzed Architecture has different scores, which should be the delegate? The policy for dealing with this question is totally determined by real players, in this problem we choose the higher one — we choose the highest possible score among all Analyzed Target Architecture. Your task in this problem is: given a player’s Holding Tiles, please determine all this player’s Expected Tiles (if exists) and their corresponding scores.
7/8 Input The first line of input file is a integer T (T ≤ 100) indicating number of test cases, then T lines are following. Each line describes a case of Holding Tiles: two separated strings, the first string giving the Hidden Tiles and the second one giving the Declared Tiles. If there are no Declared ones, the second string would be ‘NONE’ (quotes for clarity). Each tile contains two characters, the first one is a digit character which indicates this tile’s number and the second is a capital letter within ‘D’,‘B’ and ‘M’, that ‘D’ for Dots and ‘B’ for Bamboo and ‘M’ for Myriads, indicating tile’s Suit. For example, ‘7M’ means Seventh Myriad and ‘1B’ means First Bamboo (also known as ‘Yao-Jhee’). You may assume that all the input cases are valid in the rule of Sichuan Mahjong. Output For each case, firstly output a single line containing the case number counting from 1. Then, if there’s no Expected Tiles, output a single lines containing string of ‘NONE’ (quotes for clarity); otherwise, output all the player’s Expected Tiles (with the same format of input) and then output their corresponding scores after each Expected Tiles, separated with a colon (‘:’) and a space. All the Expected Tiles are printed in separated lines. Any extra blanks (spaces or empty lines) will cause ‘Wrong Answer’. The outputted Expected Tiles should be sorted in this way: first sorted by Suits, ‘D’ at first and then ‘B’ and ‘M’ in the last; second sorted by their numbers, smaller number has higher priority. Hints: Consider the third case of sample input, it seems that adding a tile ‘1D’ may construct the Target Architecture, however, there does not exist another ‘1D’ in all the tiles. Sample Input 7 8D8D8D5D2D2D2D 6D6D6D7D7D7D 8D8D8D5D2D2D2D6D6D6D7D7D7D NONE 1D1D1D1D 3D3D3D4D4D4D5D5D5D 2D2D2D5D5D5D2M2M2M5M5M8M8M NONE 1D1D1D1D2D2D2D2D3D3D3D3D9M NONE 1D1D1D1D9D9D9D9D1M1M1M1M9M NONE 2D2D3D3D4D5D5D6D6D7D7D8D8D NONE Sample Output Case #1: 5D: 4 Case #2: 4D: 3 5D: 4 6D: 4 7D: 4 8D: 4 Case #3: NONE Case #4: 5M: 4 8M: 4 Case #5: 9M: 6 Case #6:
8/8 9M: 8 Case #7: 1D: 3 4D: 5