题目描述

给定一个标号从 $0$ 开始的 $N\times N$ 方阵，其中包含从 $0$ 到 $N^2-1$ 的所有整数，且每个整数恰好出现一次。

目标是把方阵变成有序状态，即对于每个 $0\le i,j<N$，第 $i$ 行第 $j$ 列的数字都等于

$$i\times N+j.$$

你可以使用下面两种操作。

下移操作

操作格式为：

D a_0 a_1 ... a_{N-1}

其中 $a_0,a_1,\ldots,a_{N-1}$ 是当前方阵最上面一行数字的一种重新排列。

执行该操作后，当前方阵最上面一行被移除，并把由

$$a_0,a_1,\ldots,a_{N-1}$$

从左到右组成的新行加入到方阵底部。

右移操作

操作格式为：

R b_0 b_1 ... b_{N-1}

其中 $b_0,b_1,\ldots,b_{N-1}$ 是当前方阵最左侧一列数字的一种重新排列。

执行该操作后，当前方阵最左侧一列被移除，并把由

$$b_0,b_1,\ldots,b_{N-1}$$

从上到下组成的新列加入到方阵右侧。

重新排列是指只改变这些数字的顺序，不添加或删除任何数字；也可以保持原顺序不变。

你的目标是用少于 $3N$ 次操作解决这个问题。不过，如果使用更多操作，或者没有完全解决问题，也可能获得部分分数，具体见“计分方式”。

操作示例

如果当前方阵为：

行/列 0 1 2
0     2 4 6
1     8 1 5
2     7 3 0

执行操作：

D 6 2 4

会得到：

行/列 0 1 2
0     8 1 5
1     7 3 0
2     6 2 4

而执行操作：

R 2 8 7

会得到：

行/列 0 1 2
0     4 6 2
1     1 5 8
2     3 0 7

对于 $N=3$，目标方阵为：

行/列 0 1 2
0     0 1 2
1     3 4 5
2     6 7 8

输入格式

第一行包含一个整数 $N$。

接下来 $N$ 行，每行包含 $N$ 个整数，表示初始方阵。

输出格式

第一行输出一个整数 $M$，表示操作次数。

接下来 $M$ 行，每行输出一次操作，格式为以下两种之一：

D a_0 a_1 ... a_{N-1}

或

R b_0 b_1 ... b_{N-1}

其中 D 表示下移操作，R 表示右移操作，后面的 $N$ 个整数必须分别是当前最上面一行或当前最左侧一列的某种重新排列。

样例 1

输入

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

解释

样例输出在少于 $9$ 次操作中达到了目标状态，获得 $100\%$ 的分数。

样例 2

输入

2
2 1
0 3

输出

0

解释

该输出没有解决问题，因为只有 $1$ 和 $3$ 两个数字处于正确位置。此时正确位置数量为 $2$，总格子数为 $4$，因此得分为

$$50\times\frac{2}{4}=25\%.$$

数据范围

• $2\le N\le 9$。

本题有 $8$ 个子任务，分别对应不同的 $N$：

• $N=2,3,4,5$ 的子任务各 $12$ 分；
• $N=6,7,8,9$ 的子任务各 $13$ 分。

计分方式

令 $M$ 表示你输出的操作次数。令

$$A=3N,\qquad B=2N^2.$$

如果输出不合法，或者 $M>B$，则得 $0$ 分。

否则，设最终方阵中处于正确目标位置的数字数量为 $C$。

如果

$$C<N^2,$$

则没有完全解决问题，只能获得

$$50\times\frac{C}{N^2}\%$$

的分数。

否则，即 $C=N^2$：

• 如果 $M<A$，获得该测试点 $100\%$ 的分数；
• 如果 $A\le M\le B$，获得

$$40\times\left(\frac{B-M}{B-A}\right)^2+50$$

百分比的分数。

每个子任务的分数是其中所有测试点得分的最小值。