Big Brush
Contest: Codeforces Round 771 (Div. 2)
Difficulty rating: 2000
Tags: constructive algorithms, data structures, greedy, implementation

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.

Input format:
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)$$$.

Output format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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

Example input:
4 4
5 5 3 3
1 1 5 3
2 2 5 4
2 2 4 4

Example output:
6
1 3 3
3 3 4
2 2 5
1 1 5
2 1 1
3 1 2

Example input:
3 4
1 1 1 1
2 2 3 1
2 2 1 1

Example output:
-1

Editorial:
Let's try to build the solution from the last operation to the first operation. The last operation can be any $$$2 \times 2$$$ square painted in a single color. If there is no such square, it is clearly impossible. Otherwise, this square being the last operation implies that we could previously color its cells in any color, multiple times, without any consequences. We will name these special cells.
What happens when we run out of $$$2 \times 2$$$ squares painted in a single color? Well, we can use the special cells described above. The next operation considered can be any $$$2 \times 2$$$ square such that all its non-special cells are painted in the same color. If there is no such square, it is clearly impossible.
We now have a correct solution. It consists of at most $$$nm$$$ operation because at each step we turn at least one non-special cell into a special one and there are $$$nm$$$ cells. We can implement this solution similar to BFS. First, insert all $$$2 \times 2$$$ squares painted in a single color into a queue. Then, at each step take the square in the front of the queue, add it to the solution and make all its non-special cells special. When making a cell special, check all $$$2 \times 2$$$ squares that contain it and if some of them meet the condition after the current step, insert them into the queue. Note that there are at most $$$9$$$ such squares.
Time complexity: $$$O(nm)$$$.