정사각형 격자 퍼즐

이 퍼즐에서는 $0$부터 시작하는 $N \times N$ 정사각형 격자가 주어지며, 격자에는 $0$부터 $N \times N - 1$까지의 서로 다른 정수가 들어 있다. 목표는 모든 $0 \le i, j < N$에 대해 $i$행 $j$열의 수가 $i \times N + j$와 같은 정렬 상태에 도달하는 것이다. 이 목표는 다음 두 종류의 이동으로 달성할 수 있다.

• D 이동(아래 이동): "D $a[0]$ $a[1]$ $\dots$ $a[N - 1]$" 형식으로 쓴다. $a[0], a[1], \dots, a[N - 1]$은 맨 위 행에 있는 수들을 재배열한 것이다. 이 이동은 맨 위 행을 없애고, $a[0]$부터 $a[N - 1]$까지를 왼쪽에서 오른쪽 순서로 적은 새 행을 격자 맨 아래에 추가한다.
• R 이동(오른쪽 이동): "R $b[0]$ $b[1]$ $\dots$ $b[N - 1]$" 형식으로 쓴다. $b[0], b[1], \dots, b[N - 1]$은 맨 왼쪽 열에 있는 수들을 재배열한 것이다. 이 이동은 맨 왼쪽 열을 없애고, $b[0]$부터 $b[N - 1]$까지를 위에서 아래 순서로 적은 새 열을 격자 오른쪽에 추가한다.

재배열은 수를 더하거나 빼지 않고 순서만 바꾸는 것을 말하며, 원래 순서를 그대로 둘 수도 있다.

예를 들어 현재 격자가 다음과 같다고 하자.

이동 "D $6$ $2$ $4$"를 수행하면 다음 격자가 된다.

반면 이동 "R $2$ $8$ $7$"을 수행하면 다음과 같다.

$N = 3$일 때 목표 격자는 다음과 같다.

$3 \times N$번보다 적은 이동으로 퍼즐을 푸는 것이 목표다. 이동 횟수가 더 많거나 퍼즐을 풀지 못해도 부분 점수를 받을 수 있다.

첫 줄에 정수 $N$이 주어진다. 다음 $N$개 줄에는 초기 격자가 주어지며, 각 줄에 $N$개의 수가 있다.

첫 줄에 이동 횟수 $M$을 출력한다. 다음 $M$개 줄에는 이동을 한 줄에 하나씩 출력한다.

$2 \le N \le 9$이다. $2$부터 $9$까지의 각 $N$에 대해 테스트 케이스 수는 같다.