P6347 [CCO 2017] Shifty Grid

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.

The first line contains two integers $n,m$. The next $n$ lines each contain $m$ positive integers representing the 2D array.

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

#### 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](https://cemc.math.uwaterloo.ca/contests/computing/2017/) Day2 “[Shifty Grid](https://cemc.math.uwaterloo.ca/contests/computing/2017/stage%202/day2.pdf)”. Note: This translation is from [LOJ](https://loj.ac/problem/2755). Translated by ChatGPT 5