您在画布上发现了一幅画,尺寸为 $$$n \times m$$$。画布可以表示为具有 $$$n$$$ 行和 $$$m$$$ 列的网格。每个细胞都有某种颜色。单元格 $$$(i, j)$$$ 的颜色为 $$$c_{i,j}$$$。
在这幅画附近,你还发现了一个 $$$2 \times 2$$$ 正方形形状的画笔,因此画布肯定是按以下方式绘制的:最初,没有绘制任何单元格。然后,执行了多次以下绘画操作:
- 选择两个整数 $$$i$$$ 和 $$$j$$$ ($$$1 \le i < n$$$, $$$1 \le j < m$$$) 和一些颜色 $$$k$$$ ($$$1 \le k \le nm$$$)。
- 用 $$$k$$$ 颜色绘制单元格 $$$(i, j)$$$、$$$(i + 1, j)$$$、$$$(i, j + 1)$$$、$$$(i + 1, j + 1)$$$。
所有单元格必须至少绘制一次。一个单元格可以被多次绘制。在这种情况下,其最终颜色将是最后一种。
找到最多 $$$nm$$$ 操作的任何序列,这些操作可能导致你找到的绘画或声明这是不可能的。
输入
输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n, m \le 1000$$$) — 画布的尺寸。
在接下来的 $$$n$$$ 输入行的第 $$$i$$$ 行上,将有 $$$m$$$ 整数。其中第 $$$j$$$ 是 $$$a_{i,j}$$$ ($$$1 \le a_{i,j} \le nm$$$) — 单元格 $$$(i, j)$$$ 的颜色。
输出
如果没有解决方案,则打印单个整数 $$$-1$$$。
否则,在第一行打印一个整数 $$$q$$$ ($$$1 \le q \le nm$$$) — 操作数。
接下来,按顺序打印操作。在接下来的 $$$q$$$ 行的第 $$$k$$$ 行上,打印三个整数 $$$i$$$, $$$j$$$, $$$c$$$ ($$$1 \le i < n$$$, $$$1 \le j < m$$$, $$$1 \le c \le nm$$$) - 第 $$$k$$$ 操作的描述。
如果有多个解决方案,请打印其中一个。
示例
输入 #1
4 4 5 5 3 3 1 1 5 3 2 2 5 4 2 2 4 4
输出 #1
6 1 3 3 3 3 4 2 2 5 1 1 5 2 1 1 3 1 2
输入 #2
3 4 1 1 1 1 2 2 3 1 2 2 1 1
输出 #2
-1
注意
在第一个测试用例中,解决方案不是唯一的。这是其中之一:
在第二个测试用例中,无法获得给定的绘画,因此答案是 $$$-1$$$。