밀어서 맞추는 격자

문제

빈칸 없이 타일로 채워진 직사각형 격자가 있다. 격자는 $N$ 행 $M$ 열이라서 타일이 모두 $NM$ 개이고, 타일에는 $0$ 부터 $NM-1$ 까지 서로 다른 정수가 하나씩 적혀 있다.

격자를 바꾸는 방법은 밀기 연산뿐이다. 한 번의 밀기는 한 행 전체를 왼쪽이나 오른쪽으로 몇 칸 밀거나, 한 열 전체를 위나 아래로 몇 칸 민다. 경계 밖으로 밀려난 타일은 반대쪽으로 돌아 들어온다. 예를 들어 격자

0   1   2   3
4   5   6   7
8   9   10  11
12  13  14  15

에서 둘째 열을 아래로 한 칸 밀면 다음과 같다.

0   13  2   3
4   1   6   7
8   5   10  11
12  9   14  15

왼쪽으로 $K$ 칸 밀기는 오른쪽으로 $M-K$ 칸 밀기와 결과가 같고, 위로 $K$ 칸 밀기는 아래로 $N-K$ 칸 밀기와 결과가 같다. 그래서 답에는 오른쪽 밀기와 아래쪽 밀기만 쓴다.

첫째 행에 $0$ 부터 $M-1$ 까지, 둘째 행에 $M$ 부터 $2M-1$ 까지, 같은 방식으로 마지막 행에 $(N-1)M$ 부터 $NM-1$ 까지 순서대로 놓인 상태를 완성된 상태라고 한다. 뒤섞인 격자를 완성된 상태로 되돌려라.

입력

첫째 줄에 정수 $N$ 과 $M$ 이 주어진다 ( $2 \le N, M \le 100$ ). $N$ 과 $M$ 은 모두 짝수다. 다음 $N$ 개 줄에는 격자의 한 행이 왼쪽부터 차례로 정수 $M$ 개로 주어진다. 타일 $NM$ 개는 $0$ 부터 $NM-1$ 까지의 순열이다.

출력

행은 위에서부터 $1$ 번부터 $N$ 번까지, 열은 왼쪽에서부터 $1$ 번부터 $M$ 번까지 번호를 매긴다. 한 줄에 연산 하나를 출력한다. 1 i r ( $1 \le i \le N$ , $0 \le r < M$ )은 $i$ 번 행을 오른쪽으로 $r$ 칸 밀고, 2 j d ( $1 \le j \le M$ , $0 \le d < N$ )는 $j$ 번 열을 아래로 $d$ 칸 민다. $i$ 번 행 $j$ 번 열에 놓여야 하는 타일은 $(i-1)M + (j-1)$ 번이다.

같은 격자를 푸는 연산 순서는 여러 가지라서, 답은 아래 절차 하나로 고정한다. 이 절차가 만들어 내는 연산을 그대로 출력한다.

1 i r로 출력되는 연산을 R(i, r), 2 j d로 출력되는 연산을 C(j, d)라고 쓴다. $1 \le a \le M-1$ , $1 \le b \le N-1$ 일 때 TURN(i, j, a, b)는 다음 네 연산을 이 순서로 뜻한다.

R(i, a)
C(j, b)
R(i, M-a)
C(j, N-b)

TURN(i, j, a, b)는 타일 세 개만 돌리고 나머지 타일은 원래 자리에 그대로 둔다. $i$ 번 행 $j-a$ 번 열의 타일이 $i$ 번 행 $j$ 번 열로, $i$ 번 행 $j$ 번 열의 타일이 $i-b$ 번 행 $j$ 번 열로, $i-b$ 번 행 $j$ 번 열의 타일이 $i$ 번 행 $j-a$ 번 열로 간다. 여기서 행 번호와 열 번호는 순환하므로 $0$ 번 행은 $N$ 번 행, $0$ 번 열은 $M$ 번 열을 뜻한다.

절차는 작업 격자 하나를 들고 진행한다. 작업 격자는 입력 격자로 시작하고, 연산을 출력할 때마다 그 연산을 작업 격자에 바로 적용한다. 그래서 뒤의 단계는 갱신된 격자를 읽는다.

1단계. $i = 1, 2, \dots, N-1$ 에 대해, 각 $i$ 안에서 $j = 1, 2, \dots, M$ 에 대해 다음을 한다. $v = (i-1)M + (j-1)$ 이라 하고, 작업 격자에서 $v$ 가 놓인 칸을 $x$ 번 행 $y$ 번 열이라고 하자.

$x = i$ 이고 $y = j$ 이면 아무것도 출력하지 않는다.
그렇지 않고 $x = i$ 이면 TURN(i, j, (j-y) mod M, N-1)을 출력한다.
그 외에는 $x > i$ 이다. $d$ 를 (j-y) mod M이라 하자. $d > 0$ 이면 R(x, d)를 출력한다. 이어서 TURN(x, j, M-1, x-i)를 출력한다.

2단계. 이제 작업 격자의 마지막 행에는 $(N-1)M$ 부터 $NM-1$ 까지가 어떤 순서로든 놓여 있다. $N$ 번 행 $c$ 번 열의 타일을 $t_c$ 라 하고, $p(c) = t_c - (N-1)M + 1$ 로 정의되는 $1, 2, \dots, M$ 의 순열을 $p$ 라고 하자. $p$ 가 홀순열이면 R(N, 1)을 출력한다.

3단계. $j = 1, 2, \dots, M$ 에 대해 다음을 한다. $v = (N-1)M + (j-1)$ 이라 하고, $N$ 번 행에서 $v$ 가 놓인 열을 $y$ 라고 하자. $y = j$ 이면 아무것도 출력하지 않는다. 그렇지 않으면 $t \ne j$ , $t \ne y$ 이면서 $N$ 번 행 $t$ 번 열의 타일이 $(N-1)M + (t-1)$ 이 아닌 가장 작은 열 번호를 $t$ 라고 하자. 그리고 C(t, 1), R(1, (j-t) mod M), TURN(N, j, (j-y) mod M, N-1), R(1, (t-j) mod M), C(t, N-1)을 이 순서로 출력한다.

출력한 연산의 개수를 $K$ 라고 하자. 첫째 줄에 $K$ 를 출력하고, 다음 $K$ 개 줄에 출력한 순서대로 연산을 한 줄에 하나씩 출력한다. 이 절차는 언제나 완성된 상태에 도달하며 연산을 $10^5$ 개보다 많이 만들지 않는다. 주어진 격자가 이미 완성된 상태이면 $K$ 는 $0$ 이고 출력은 0 한 줄뿐이다.