本站作为LDUOnlineJudge的测试版本进行演示,官方网站请访问http://icpc.ldu.edu.cn
[Hidden]

1259. H. Chocolate Fix


Description

Your cousin recently bought a game that involves arranging truffles on a 3 x 3 grid. Eager to one up him, you decide to write a program to solve the puzzles automatically, so that he doesn't have a chance in figuring out the puzzles against you!


The game comes with nine truffles, which are used in each puzzle. Each truffle is either vanilla, strawberry or chocolate (VSC) and the shape of each truffle is either square, round or triangular (SRT). There is exactly one truffle of each combination of attributes and all of them must be used. In each puzzle, you must place each of the nine truffles on the 3 x 3 board. For convenience, label the squares 1, 2 and 3 on the first row, from left to right, 4, 5 and 6 on the second row, and 7, 8 and 9 on the third row as illustrated below:


For each puzzle, you are given a list of clues. Each clue represents partial information about a subsection of the board. For example, the clue below means that there is some 3 x 2 window with the square strawberry truffle in its upper right corner:

There are only two such possible 3 x 2 windows on a 3 x 3 board. Thus, this clue essentially conveys the fact that the square strawberry truffle must appear in either square 2 or square 3 of the board since clues cannot be rotated:

Another example of a clue is as follows:



This clue also represents a 3 x 2 window of the board. It indicates that in the right column of the window there must be a strawberry truffle (of some shape) on the top row, the round chocolate truffle in the middle row of the column and a triangular truffle (of some flavor) on the bottom row of the column. Due to the window size, we can ascertain that this must be true of either middle or rightmost column of the game board.



The Problem:
Given a set of clues that uniquely specifies a solution to a chocolate puzzle, determine that solution.

Input

The first input line contains a positive integer, n, indicating the number of puzzles to solve. The puzzles follow. The first line of each puzzle will contain a single positive integer, c (1 ≤ c ≤ 10), representing the number of clues for that puzzle. The clues will follow. The first line of each clue will contain two space separated integers: x (1 ≤ x ≤ 3) and y (1 ≤ y ≤ 3), representing the number of rows and columns, respectively, for the clue window. The next x lines will contain the clue, with each element in the clue represented by 2 characters. The first character will come from the set {'_','S','R','T'}, indicating the shape of that element and the second character will come from the set {'_','V','S','C'}, indicating the flavor of that element. Note that the underscore character simply means that that attribute is not fixed. Each of these x lines will contain y codes; the codes separated by exactly one space.

Output

The first line of the output for each puzzle should be "Puzzle #p:”, where p is the puzzle number, starting with 1. On the next three lines, output the puzzle solution, using the same codes used in the clues. Note that since there is a unique solution to each puzzle, no underscore characters can be in any valid solution.



Leave a blank line after the output for each test case. Follow the format illustrated in Sample Output.

Samples

Input Copy
3
4
3 3
TC __ SS
__ __ __
__ TV __
2 3
__ SC __
RV __ SV
3 3
__ __ __
__ RC __
__ __ __
2 3
__ __ __
TS __ RS
5
2 3
__ __ __
__ __ RC
2 2
__ RS
SC __
2 2
SV TC
__ __
3 2
TV __
__ __
__ RV
3 2
__ TS
__ __
__ __
3
3 2
_C R_
_C __
S_ _C
1 2
TC _V
3 2
_V __
S_ S_
T_ _V
Output
Puzzle #1:
TC SC SS
RV RC SV
TS TV RS

Puzzle #2:
TV RS TS
SC SV TC
SS RV RC

Puzzle #3:
TV TC RV
SS SC RS
TS SV RC

Source

UCF2014
Problem Information

Time Limit: 1000MS (C/C++,Others×2)
Memory Limit: 128MB (C/C++,Others×2)
Special Judge: No
AC/Submit: 0 / 1
Tags:
Contests involved

1029. UCF 2014
My history solutions

You didn't submit any solution!
Submit your solution

Login Register