Shifty Grid

You are given a rectangular grid of numbered tiles with no empty cell. The grid has $N$ rows and $M$ columns, so it holds $NM$ tiles, and the tiles carry distinct integers from $0$ to $NM-1$.

The only way to change the grid is a shift operation. One shift moves a whole row left or right by some number of cells, or a whole column up or down by some number of cells. A tile pushed past a border comes back in on the opposite side. For example, in the grid

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

shifting the second column down by one gives

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

A left shift by $K$ cells has the same effect as a right shift by $M-K$ cells, and an upward shift by $K$ cells has the same effect as a downward shift by $N-K$ cells, so the answer uses right shifts and down shifts only.

The grid is solved when the first row holds $0$ to $M-1$ in order, the second row holds $M$ to $2M-1$ in order, and so on, with the last row holding $(N-1)M$ to $NM-1$ in order. Return the scrambled grid to the solved state.

The first line contains two integers $N$ and $M$ ($2 \le N, M \le 100$). Both $N$ and $M$ are even. Each of the next $N$ lines contains $M$ integers, one row of the grid from left to right. The $NM$ tiles are a permutation of $0$ to $NM-1$.

Rows are numbered $1$ to $N$ from the top and columns $1$ to $M$ from the left. Each move is printed on its own line. The line 1 i r ($1 \le i \le N$, $0 \le r < M$) shifts row $i$ right by $r$ cells, and the line 2 j d ($1 \le j \le M$, $0 \le d < N$) shifts column $j$ down by $d$ cells. The tile that belongs at row $i$, column $j$ is the number $(i-1)M + (j-1)$.

Many different move sequences solve the same grid, so the answer is pinned to one procedure. Print exactly the moves that the procedure below produces.

Write R(i, r) for the move printed as 1 i r, and C(j, d) for the move printed as 2 j d. For $1 \le a \le M-1$ and $1 \le b \le N-1$, write TURN(i, j, a, b) for these four moves in this order:

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

TURN(i, j, a, b) rotates three tiles and leaves every other tile where it was: the tile in row $i$, column $j-a$ moves to row $i$, column $j$; the tile in row $i$, column $j$ moves to row $i-b$, column $j$; and the tile in row $i-b$, column $j$ moves to row $i$, column $j-a$. Row and column numbers wrap here, so row $0$ means row $N$ and column $0$ means column $M$.

The procedure keeps one working grid. It starts as the input grid, and every emitted move is applied to it at once, so each step reads the updated grid.

Step 1. For $i = 1, 2, \dots, N-1$, and inside each $i$ for $j = 1, 2, \dots, M$, let $v = (i-1)M + (j-1)$ and let row $x$, column $y$ be the cell that holds $v$.

• If $x = i$ and $y = j$, emit nothing.
• Otherwise, if $x = i$, emit TURN(i, j, (j-y) mod M, N-1).
• Otherwise $x > i$ holds. Let $d$ be (j-y) mod M. If $d > 0$, emit R(x, d). Then emit TURN(x, j, M-1, x-i).

Step 2. The last row of the working grid now holds the numbers $(N-1)M$ to $NM-1$ in some order. Let $t_c$ be the tile in row $N$, column $c$, and let $p$ be the permutation of $1, 2, \dots, M$ given by $p(c) = t_c - (N-1)M + 1$. If $p$ is an odd permutation, emit R(N, 1).

Step 3. For $j = 1, 2, \dots, M$, let $v = (N-1)M + (j-1)$ and let $y$ be the column of row $N$ that holds $v$. If $y = j$, emit nothing. Otherwise let $t$ be the smallest column such that $t \ne j$, $t \ne y$, and the tile in row $N$, column $t$ is not $(N-1)M + (t-1)$. Emit these moves in this order: C(t, 1), then R(1, (j-t) mod M), then TURN(N, j, (j-y) mod M, N-1), then R(1, (t-j) mod M), then C(t, N-1).

Let $K$ be the number of emitted moves. Print $K$ on the first line, then the $K$ moves, one per line, in the order they were emitted. The procedure always reaches the solved state and never emits more than $10^5$ moves. When the given grid is already solved, $K$ is $0$ and the output is the single line 0.