CF1638D.Big Brush

You found a painting on a canvas of size $n \times m$. The canvas can be represented as a grid with $n$ rows and $m$ columns. Each cell has some color. Cell $(i, j)$ has color $c_{i,j}$.

Near the painting you also found a brush in the shape of a $2 \times 2$ square, so the canvas was surely painted in the following way: initially, no cell was painted. Then, the following painting operation has been performed some number of times:

• Choose two integers $i$ and $j$ ($1 \le i \lt n$, $1 \le j \lt m$) and some color $k$ ($1 \le k \le nm$).
• Paint cells $(i, j)$, $(i + 1, j)$, $(i, j + 1)$, $(i + 1, j + 1)$ in color $k$.

All cells must be painted at least once. A cell can be painted multiple times. In this case, its final color will be the last one.

Find any sequence of at most $nm$ operations that could have led to the painting you found or state that it's impossible.

你在一块大小为 $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$）；
• 将格子 $(i, j)$、$(i + 1, j)$、$(i, j + 1)$、$(i + 1, j + 1)$ 涂成颜色 $k$。

所有格子必须至少被涂色一次。一个格子可以被多次涂色；此时，其最终颜色为最后一次涂上的颜色。

请找出任意一个长度不超过 $nm$ 的操作序列，使其能生成你所发现的这幅画；若不存在这样的序列，则判定为不可能。

The first line of input contains two integers $n$ and $m$ ($2 \le n, m \le 1000$) — the dimensions of the canvas.

On the $i$-th of the next $n$ lines of input, there will be $m$ integers. The $j$-th of them is $a_{i,j}$ ($1 \le a_{i,j} \le nm$) — the color of cell $(i, j)$.

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

接下来的 $n$ 行中，第 $i$ 行包含 $m$ 个整数。其中第 $j$ 个整数为 $a_{i,j}$（$1 \le a_{i,j} \le nm$）——表示单元格 $(i, j)$ 的颜色。

If there is no solution, print a single integer $-1$.

Otherwise, on the first line, print one integer $q$ ($1 \le q \le nm$) — the number of operations.

Next, print the operations in order. On the $k$-th of the next $q$ lines, print three integers $i$, $j$, $c$ ($1 \le i \lt n$, $1 \le j \lt m$, $1 \le c \le nm$) — the description of the $k$-th operation.

If there are multiple solutions, print any.

如果无解，请输出单个整数 $-1$。

否则，在第一行输出一个整数 $q$（$1 \le q \le nm$）—— 表示操作次数。

接下来，按顺序输出各操作。在接下来的 $q$ 行中，第 $k$ 行输出三个整数 $i$、$j$、$c$（$1 \le i \lt n$，$1 \le j \lt m$，$1 \le c \le nm$）—— 表示第 $k$ 个操作的描述。

若有多种解法，输出任意一种即可。

In the first test case, the solution is not unique. Here's one of them:

In the second test case, there is no way one could obtain the given painting, thus the answer is $-1$.

在第一个测试用例中，解不唯一。以下是其中一个解：

在第二个测试用例中，无法通过任何方式得到给定的画作，因此答案为 $-1$。