Problem Description

There is an $N \times N$ matrix, whose elements are labeled from $0 \sim N^2 - 1$. We want to make the element in row $i$ and column $j$ become $i \cdot N + j$ using fewer than $3N$ operations.

You can perform two kinds of operations on the matrix:

• D a[0] a[1] ... a[N-1]: Rearrange the first row of the matrix, then cyclically shift each column upward by one. You must ensure that the given $a$ is a permutation of the first row of the matrix.

• R b[0] b[1] ... b[N-1]: Rearrange the first column of the matrix, then cyclically shift each row leftward by one. You must ensure that the given $b$ is a permutation of the first column of the matrix.

For example, if the current matrix is:

If we perform D 2 6 4 on the original matrix, the matrix becomes:

If we perform R 2 8 7 on the original matrix, the matrix becomes:

Even if you use $\geq 3N$ operations, or some numbers are not restored, you can still get partial score. See the Scoring section.

Input Format

The first line contains an integer $N$.

The next $N$ lines each contain $N$ integers $F_{i,j}$, representing the initial matrix.

Output Format

The first line contains an integer $M$, representing the number of operations.

The next $M$ lines each describe one operation, in the format given above.

3
1 4 2
3 7 5
6 8 0

4
R 3 6 1
D 2 3 4
D 5 6 7
R 2 5 8

2
2 1
0 3

0

Hint

Scoring

Let $A = 3N$, $B = 2N^2$, and let $C$ be the number of positions that satisfy the requirement after the operations.

If your program does not terminate normally, or the output format is wrong, or $M > B$, then you get $0$ points for this test point.

Otherwise, if $C < N^2$, you get $50\% \cdot \frac{C}{N^2}$ of the score for this test point.

Otherwise, if $A \leq M \leq B$, you get $(40 \cdot (\frac{B - M}{B - A})^2 + 50)\%$ of the score for this test point.

Otherwise, you get the full score.

Sample Explanation

In the first sample, $4$ operations are used to restore the matrix, so you can get a score of $100\%$.

In the second sample, $0$ operations are used to restore $\frac{2}{4} = 50\%$ of the positions, so you can get a score of $25\%$ for this test point.

Constraints

For $100\%$ of the testdata, it is guaranteed that $2 \leq N \leq 9$, and $N$ is uniformly distributed among the test points.

Translated by ChatGPT 5