题目描述

给你一个二维数组。我们只能通过 移动(Shift) 操作来改动这个数组。一次移动操作可以将一行元素向左（或向右）移几个单位；或将一列元素向上（或向下）移几个单位。如果被移动的元素越界，则将越界元素移动到该行或列的另一侧。

举个例子：

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

将第二列向下移动 $1$ 个单位（或向上移动 $3$ 个单位），二维数组将会变成这样：

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

一次移动 $k$ 个单位的 左移 操作等价于移动 $n-k$ 个单位的 右移 操作。在列上的变换同样。

因此，我们规定只有 下移 和 右移 操作。

在一个 $n \times m$ 的二维数组中，所有的数各不相同，且 $Num_{ij} \in [0,n-1]$（规定第 $i$ 行 $j$ 列的数编号为 $Num_{ij}$）。

在第一个例子中，我们给你的二维数组非常 和谐，我们叫它 和谐数组 (Solved)。一个二维数组当且仅当第一行的元素按照升序编号分别为从 $0$ 到 $m-1$，第二行元素为从 $m$ 到 $2m-1$，以此类推时，我们称它为 和谐数组。

你的任务是找到一系列的操作，使得二维数组变成 和谐数组。

输入格式

第一行为两个整数 $n,m$；

下面的 $n$ 行将会包含 $m$ 个代表二维数组的正整数。

输出格式

第一行输出移动的步数 $k$（$1\leq k\leq 10 ^ 5$）。

下面的 $k$ 行输出：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$ 格。

如果数组本身就是和谐数组，输出 $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

提示

样例解释

对于样例 $1$：经过如下变换

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

对于样例 $2$：经过如下变换

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

数据范围及约定

本题采用多测试点捆绑测试，共有 $3$ 个子任务。

• Subtask 1（20 points）：$2 \le n \times m \le 8$；
• Subtask 2（40 points）：$1 \le k \le 2$；
• Subtask 3（40 points）：无特殊限制。

对于全部的测试点，保证 $2 \le n,m \le 100$，$1 \le k \le 10^5$，保证 $n,m$ 为偶数。

来源：CCO 2017 Day2「Shifty Grid」。

说明：翻译来自 LOJ。