Big Brush

题意翻译

给定一个大小为 $n \times m$ 的网格，每一个网格都有颜色 $c_{i,j}$。 最初，你有一个没有颜色的网格，可以进行若干次操作： - 选择两个整数 $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$ 次操作，将空白网格涂成给定的网格。 如果不能，输出 $-1$，否则输出方案。 **数据范围**： $2\le n,m \le 1000,1 \le c_{i,j} \le nm$。

题目描述

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 < n $ , $ 1 \le j < 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.

输入输出格式

输入格式

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) $ .

输出格式

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 < n $ , $ 1 \le j < m $ , $ 1 \le c \le nm $ ) — the description of the $ k $ -th operation. If there are multiple solutions, print any.

输入输出样例

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

说明

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 $ .