Intellectual Property#6268

Intellectual Property

2 seconds

256 megabytes

Very hard

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$ 9 \times 9, divided into $3 \times 3$ 3 \times 3 subtables of $3 \times 3$ 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$ 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)$ (1, 2, 3), $(4, 5, 6)$ (4, 5, 6), $(7, 8, 9)$ (7, 8, 9); - swap two rows in one triple of rows; - swap two triples of columns: $(1, 2, 3)$ (1, 2, 3), $(4, 5, 6)$ (4, 5, 6), $(7, 8, 9)$ (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.

![prb6268](https://static.e-olymp.com/content/aa/aab6a854d1a7e4d6f25ff2b4e7688f0372797d28.jpg)

Help Kopi to find similar puzzles in his database.

Input

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

The rest contains description of $n$ puzzles: $P_{1}, P_{2}, \dots, P_{n}$ P_1, P_2, \ldots, P_n. 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 data.

The puzzles are not guaranteed to be solvable.

Output

Check if the puzzle $P_{1}$ P_1 is similar to puzzles $P_{2}$ P_2, $P_{3}$ P_3, ..., $P_{n}$ P_n (in this order), than check if the puzzle $P_{2}$ P_2 is similar to puzzles $P_{3}$ P_3, $P_{4}$ P_4, ..., $P_{n}$ P_n (in this order) and so on.

If the puzzle $P_{i}$ P_i is similar to the puzzle $P_{j}$ P_j ( $1 \leq i < j \leq n$ 1 \le i < j \le n) output "Yes", otherwise output "No". If the answer is positive, the next line should contain an integer $q_{ij}$ q_{ij} - the number of operations required to transform the puzzle $P_{i}$ P_i to the puzzle $P_{j}$ P_j. The number of operations is not required to be minimal, however it must not exceed $1000$ . In the following $q_{ij}$ q_{ij} lines write the operations that transform the puzzle $P_{i}$ P_i to the puzzle $P_{j}$ P_j, 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 $(3 a - 2, 3 a - 1, 3 a)$ (3a-2, 3a-1, 3a) and $(3 b - 2, 3 b - 1, 3 b)$ (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 $(3 a - 2, 3 a - 1, 3 a)$ (3a-2, 3a-1, 3a) and $(3 b - 2, 3 b - 1, 3 b)$ (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 data, starting from one.

Examples

Example 1