Description

You are given a 2D array. We can only modify this array using shift (Shift) operations. One shift operation can shift all elements in one row to the left (or to the right) by several positions, or shift all elements in one column upward (or downward) by several positions. If an element goes out of bounds during the shift, it is wrapped around to the other side of that row or column.

For example:

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

If we shift the second column downward by $1$ position (or upward by $3$ positions), the 2D array becomes:

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

A left shift by $k$ positions is equivalent to a right shift by $n-k$ positions. The same applies to shifts on columns.

Therefore, we only allow down shifts and right shifts.

In an $n \times m$ 2D array, all numbers are distinct, and $Num_{ij} \in [0,n-1]$ (the number in row $i$ and column $j$ is denoted as $Num_{ij}$).

In the first example, the 2D array we gave you is very harmonious, and we call it a Solved array. A 2D array is called Solved if and only if the first row contains the numbers from $0$ to $m-1$ in increasing order, the second row contains the numbers from $m$ to $2m-1$ in increasing order, and so on.

Your task is to find a sequence of operations to make the 2D array become a Solved array.

Input Format

The first line contains two integers $n,m$.

The next $n$ lines each contain $m$ positive integers representing the 2D array.

Output Format

The first line outputs the number of shifts $k$ ($1\leq k\leq 10 ^ 5$).

The next $k$ lines output either 1 i r ($1 \le i \le n$, $0 \le r < m$), meaning shifting row $i$ to the right by $r$ cells, or 2 j d ($1 \le j \le m$, $0 \le d <n$), meaning shifting column $j$ downward by $d$ cells.

If the array is already Solved, output $0$.

2 4
4 2 3 0
1 5 6 7

2
2 1 1
1 1 1

4 2
2 3
5 0
4 1
6 7

7
1 1 1
2 1 1
1 2 1
1 3 1
2 1 2
1 1 1
2 1 1

Hint

Sample Explanation

For sample $1$, after the following transformations:

4 2 3 0  -> 1 2 3 0 -> 0 1 2 3
1 5 6 7     4 5 6 7    4 5 6 7

For sample $2$, after the following transformations:

2 3      3 2      6 2      6 2      6 2      1 2      2 1      0 1
5 0   -> 5 0   -> 3 0   -> 0 3   -> 0 3   -> 4 3   -> 4 3   -> 2 3
4 1      4 1      5 1      5 1      1 5      6 5      6 5      4 5
6 7      6 7      4 7      4 7      4 7      0 7      0 7      6 7

Constraints and Notes

This problem uses bundled testdata and has $3$ subtasks.

• Subtask 1 (20 points): $2 \le n \times m \le 8$.
• Subtask 2 (40 points): $1 \le k \le 2$.
• Subtask 3 (40 points): No special restrictions.

For all test cases, it is guaranteed that $2 \le n,m \le 100$, $1 \le k \le 10^5$, and $n,m$ are even.

Source: CCO 2017 Day2 “Shifty Grid”.

Note: This translation is from LOJ.

Translated by ChatGPT 5