题目描述

Erast Kopi is famous Sudoku puzzle designer. Resounding success of his puzzle compilations caused a number of imitations and plagiarisms. Prior to sending a lawsuit he decided to get more evidence.

Sudoku puzzle is a table $9 \times 9$ , divided into $3 \times 3$ subtables of $3 \times 3$ cells each. Each cell may contain a digit from $1$ to $9$ . The task is to fill empty cells with digits in a way that each row, each column and each of the $9$ subtables $3 \times 3$ contains each digit from $1$ to $9$ exactly once.

Kopi has a database of Sudoku puzzles and he wants to check if it contains similar puzzles. The puzzle $P$ is similar to the puzzle $Q$ , if it is possible to transform the puzzle $P$ into the puzzle $Q$ using a sequence of the following operations:

choose two digits $x$ and $y$ and replace all digits $x$ with $y$ and vice versa;

swap two triples of rows: $(1 , 2 , 3) , (4 , 5 , 6) , (7 , 8 , 9)$ ;

swap two rows in one triple of rows;

swap two triples of columns: $(1 , 2 , 3) , (4 , 5 , 6) , (7 , 8 , 9)$ ;

swap two columns in one triple of columns;

flip along top-left -- bottom-right axis. After this operation columns become rows and vice versa.

Help Kopi to find similar puzzles in his database.

输入格式

The first line of the input contains single integer $n$ -- the number of puzzles in the database $(1 \le n \le 20)$ .

The rest of the input contains description of $n$ puzzles: $P_1 , P_2$ , . . . , Pn. Each puzzle is described by nine lines that contain nine characters each. Each character is either a digit from $1$ to $9$ , or a dot $(‘. ')$ denoting an empty cell. An empty line separates consecutive puzzles in the database.

There are no spaces in the input file.

The puzzles are not guaranteed to be solvable.

输出格式

Check if the puzzle $P_1$ is similar to puzzles $P_2$ , P3 , . . . , $P_n$ (in this order), than check if the puzzle $P_2$ is similar to puzzles P3 , P4 , . . . , $P_n$ (in this order) and so on.

If the puzzle $P_i$ is similar to the puzzle $Pj (1 \le i < j \le n)$ output Yes, otherwise output No. If the answer is positive, the next line should contain an integer qij -- the number of operations required to transform the puzzle $P_i$ to the puzzle $Pj$ . The number of operations is not required to be minimal, however it must not exceed $1000$ . In the following qij lines write the operations that transform the puzzle $P_i$ to the puzzle $Pj$ , one per line.

Operations are encoded in the following way:

D $x$ y for swapping digits $x$ and $y$ ;

R a b for swapping triples of rows (3a $− 2$ , 3a $− 1 , 3a)$ and (3b $− 2$ , 3b $− 1 , 3b);$

r a b for swapping rows a and $b$ , rows must belong to same triple of rows;

C a b for swapping triples of columns (3a $− 2$ , 3a $− 1 , 3a)$ and (3b $− 2$ , 3b $− 1 , 3b);$

c a b for swapping columns a and $b$ , columns must belong to same triple of columns;

F for flipping along top-left -- bottom-right axis.

The columns are numbered from left to right and the rows are numbered from top to bottom as they are given in the input file, starting from one.

4
.....1...
1........
.2.....8.
.........
8....9...
.........
....7....
...2...1.
2...4....

....2....
...7.4...
8.......9
.8...2..1
..2......
.........
.........
..1.8....
.........

1........
.........
.........
.........
.........
.........
.........
.........
.........

.....1...
1........
.2.....8.
.........
8....9...
.........
....7....
...2...1.
2...4....

Yes
7
C 1 2
D 5 3
F
r 7 9
c 6 5
C 2 3
D 1 8
No
Yes
0
No
Yes
8
R 1 2
C 2 3
c 4 5
F
r 5 6
c 7 9
D 1 8
D 3 5
No

提示

Time limit: 2 s, Memory limit: 256 MB.