#2755. 「CCO 2017」移动数组

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

题目描述

译自 CCO 2017 Day2 「Shifty Grid

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

举个例子:

aa

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

a

一次移动 KKK 个单位的左移操作等价于移动 N−KN-KNK 个单位的右移操作。在列上的变换同样。

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

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

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

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

输入格式

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

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

输出格式

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

  1. 第一行输出移动的步数 KKK
  2. 下面的 KKK 行输出:1 i r(1≤i≤N,0≤r<M)1 \ i \ r (1 \le i \le N, 0 \le r \lt M)1 i r(1iN,0r<M),代表使第 iii右移 rrr 格,或 2 j d(1≤j≤M,0≤d<N) 2 \ j \ d (1 \le j \le M, 0 \le d \lt N)2 j d(1jM,0d<N),代表使第 jjj下移 ddd 格。

样例

样例输入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,MN,M 永远为偶数,K≤105K \le 10^5K105

对于 20%20 \% 20% 的数据,N×M≤8N \times M \le 8N×M8
对于另外 40%40 \%40% 的数据,K≤2K \le 2K2
对于 100%100 \% 100% 的数据,2≤N,M≤1002 \le N,M \le 1002N,M100

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