画画

题目描述

现有一个 $n \times m$ 的画布，上面每一个单元格 $(i,j)$ 都有一个正整数表示的颜色 $c_{i, j}$，$(1\le c_{i,j} \le n\times m)$。

你可以在一个 $n\times m$ 的空白画布上进行以下操作至多 $n \times m$ 次：

在画布上选择一个 $2 \times 2$ 的正方形，将这整个正方形涂成任意一种颜色 $p$，$1\le p\le n \times m$。

所有单元格必须至少涂一次。一个单元格可以多次绘制。在这种情况下，它的最终颜色将是最后一种颜色。

现在问是否有一种方案使得你最后染色的画布与画布 $c$ 相同。如果不存在合法的染色方案请输出 -1。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$，$(2\le n,m \le 1000)$，表示画布的尺寸。

接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 个整数表示 $c_{i, j}$，$(1\le c_{i, j}\le n \times m)$，表示画布每一个单元格的颜色。

输出格式

如果没有解决方案，请输出一行一个整数 -1。

否则，在第一行输出一个整数 $q$，$(1\le q \le n \times m)$，表示操作次数。

接下来，按顺序输出操作，输出 $q$ 行，每行三个整数 $x, y, p$，表示你选择的正方形坐上角 $(x,y)$，$(1\le x \le n - 1, 1 \le y \le m - 1)$，以及这个方格将会染成的颜色 $p$。

如果存在多个解决方案，请输出任何一个。

样例输入 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

样例解释

对于第一个输入这是一种合法的染色方案：

对于第二个输入不可能找到一种合适的解决方案。