Description

In this puzzle, you are given a $0$-indexed $N \times N$ square grid consisting of distinct integers from $0$ to $N \times N - 1$, inclusive. Your goal is to reach the ordered state where the number at the intersection of the $i$-th row and the $j$-th column is equal to $i \times N + j$ for each $0 \leq i, j < N$. You can achieve this goal using two types of moves:

• Down move: "D $a[0]\ a[1]\ \ldots\ a[N - 1]$", where $a[0], a[1], \ldots ,a[N - 1]$ is some rearrangement of the numbers from the topmost row of the grid. With this move, the topmost row is removed and the new row created with the numbers $a[0], a[1], \ldots ,a[N - 1]$ from left to right is added to the bottom of the grid.
• Right move: "R $b[0]\ b[1]\ \ldots\ b[N - 1]$", where $b[0], b[1], \ldots ,b[N - 1]$ is some rearrangement of the numbers from the leftmost column of the grid. With this move, the leftmost column is removed and the new column created with the numbers $b[0], b[1], \ldots ,b[N - 1]$ from top to bottom is added to the right of the grid.

Rearrangement refers to changing the order of the numbers without adding or removing any of them, and it may preserve the original order.

For example, if the current grid is:

By performing the move "D 6 2 4`", we will obtain the following grid:

However, if we instead execute move "R 2 8 7", we would get:

For $N = 3$, the target grid would look like this:

You aim to solve the puzzle with fewer than $3 \times N$ moves. However, partial points may be awarded in case you use more moves or not solve the puzzle. Refer to the scoring section for details.

Input Format

The first line contains a single integer: $N$.

The following $N$ lines describe the initial grid, with $N$ numbers on each line.

Output Format

The first line should contain a single integer, $M$, the number of moves. Each of the following $M$ lines should contain a single move.

Scoring

Let’s denote $M$ as the amount of moves in your solution. Additionally, define $A = 3 \times N$ and $B = 2 \times N^2$.

If your output is invalid, or if $M > B$, you receive $0$ points. Otherwise, your score depends on the amount of numbers in the correct target positions (denoted as $C$).

If $C < N \times N$ the puzzle is not solved and you will only receive $(50 \times \frac{C}{N\times N})\%$ of points for a test.

Otherwise:

• If $M < A$, you will receive $100\%$ of points for a test.
• If $A \leq M \leq B$, you will receive $(40 \times \left(\frac{B-M}{B-A}\right)^2 + 50)\%$ of points for a test.

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

This solution achieves the desired result in fewer than $9$ moves, earning the full points.

2
2 1
0 3

0

The puzzle isn't solved since only two numbers ($1$ and $3$) out of $4$ are in the correct position. This output would receive $50 \times \frac{2}{4} = 25\%$ of points for a test.

Constraints

• $2 \leq N \leq 9$

Subtasks

• There are no subtasks.
• There is an equal number of cases for each $N$ from $2$ to $9$.