#2755. 「CCO 2017」移动数组

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Anfangen

题目描述

译自 CCO 2017 Day2 「Shifty Grid

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

举个例子:

aa

将第二列向下移动 11 个单位(或向上移动 33 个单位),二维数组将会变成这样:

a

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

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

在一个 NMN \cdot M 的二维数组中,所有的数各不相同,且 Numij[0,N1]\text{Num}_{ij} \in [0,N-1](规定第 iijj 列的数编号为 Numij\text{Num}_{ij})。

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

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

输入格式

第一行为两个整数 N,MN,M

下面的 NN 行将会包含 MM 个代表二维数组的正整数。

输出格式

按照下列标准,输出一系列的移动操作。

  1. 第一行输出移动的步数 KK
  2. 下面的 KK 行输出:1 i r(1iN,0r<M)1 \ i \ r (1 \le i \le N, 0 \le r \lt M),代表使第 ii右移 rr 格,或 2 j d(1jM,0d<N) 2 \ j \ d (1 \le j \le M, 0 \le d \lt N),代表使第 jj下移 dd 格。

样例

样例输入1

2 4
4 2 3 0
1 5 6 7

样例输出 1

2
2 1 1
1 1 1

样例解释 1

经过如下变换:

样例输入 2

4 2
2 3
5 0
4 1
6 7

样例输出 2

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

样例解释 2

经过如下变换:

数据范围与提示

N,MN,M 永远为偶数,K105K \le 10^5

对于 20%20 \% 的数据,N×M8N \times M \le 8
对于另外 40%40 \% 的数据,K2K \le 2
对于 100%100 \% 的数据,2N,M1002 \le N,M \le 100

如果数组本身就是和谐数组,输出 00