EOJ Monthly 2019.2 (based on February Selection)

C. 魔板

单点时限: 3.0 sec

内存限制: 256 MB

“闭上眼睛,好好回想之前的努力,自信会喷涌而出。”

QQ 小方闭上眼睛,开始熟练地还原魔方。

一直是这样的挑战,显得索然无味。于是 QQ 小方发明了一种新的谜题:魔板。

魔板是一个由 n×m 个三角形组成的平行四边形,魔板有 nm 列个端点。行从下至上标记为 1n,列从左到右标记为 1m。每个端点都由坐标 (x,y) 表示,其中 x 是行,y 是列。每个端点都用一个 1nm 之间的唯一整数值表示,代表这个端点的初始标号。

  • 第一行的端点从左到右依次标号为 1,2,3,,m
  • 第二行的端点依次标号为 m+1,m+2,,2m
  • ……

如下图是一个 3×4 魔板的初始标号:

魔板有以下两种变换方式:

  • 选择一个三角形(设三角形的左下角端点坐标为 (x,y) ,则上面端点的坐标为 (x+1,y) ,右下角端点坐标为 (x,y+1)),做一次顺时针旋转(左下角到上面,上面到右下角,右下角到左下角)。
  • 选择一个菱形(设菱形的左下角端点坐标为 (x,y) ,则左上角端点的坐标为 (x+1,y) ,右下角端点坐标为 (x,y+1) ,右上角坐标为 (x+1,y+1)),做一次顺时针旋转(左下角到左上角,以此类推)。

QQ 小方又闭上眼睛了,你能打败他吗?

输入格式

第一行包含两个整数 nm (2n,m100)。

接下来 n 行,每行 m 个数,表示打乱以后的魔板。

输出格式

第一行输出一个整数 T ,表示操作的次数。

接下来的 T 行,每行三个整数 opt,x,y ,表示执行的操作。

  • opt=1 表示执行三角形顺时针旋转操作,其中左下角的坐标为 (x,y)
  • opt=2 表示执行菱形顺时针旋转操作,其中左下角的坐标为 (x,y)

在执行 T 次操作后,魔板回到了初始状态,且不存在非法操作,而且满足 T3106,则认为是正确的。

样例

Input
2 3
4 1 2
5 6 3
Output
2
1 1 1
2 1 2
Input
2 3
1 2 3
4 5 6
Output
0

提示

对于第一个样例的解释:

打乱以后魔板的状态:

5 6 3
4 1 2

执行操作 1 1 1 以后魔板的状态:

4 6 3
1 5 2

执行操作 2 1 2 以后魔板的状态:

4 5 6
1 2 3

魔板回到了初始状态。