3680. 魔板

单点时限: 3.0 sec

内存限制: 256 MB

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

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

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

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

  • 第一行的端点从左到右依次标号为
  • 第二行的端点依次标号为
  • ……

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

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

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

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

输入格式

第一行包含两个整数 ()。

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

输出格式

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

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

  • 表示执行三角形顺时针旋转操作,其中左下角的坐标为
  • 表示执行菱形顺时针旋转操作,其中左下角的坐标为

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

样例

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

魔板回到了初始状态。

2 人解决,5 人已尝试。

2 份提交通过,共有 26 份提交。

9.4 EMB 奖励。

创建: 5 月,4 周前.

修改: 5 月,4 周前.

最后提交: 5 月前.

来源: EOJ Monthly 2019.2

题目标签