Painting

Problem Description

There is now an $n \times m$ canvas. Each cell $(i,j)$ has a colour $c_{i,j}$ represented by a positive integer ($1\le c_{i,j} \le n\times m$).

You may perform the following operation at most $n \times m$ times on a blank $n \times m$ canvas:

Choose a $2 \times 2$ square on the canvas and paint the whole square with any colour $p$ ($1\le p\le n\times m$).

Every cell must be painted at least once. A cell may be painted multiple times; in that case its final colour is the last colour applied.

Now determine whether there exists a sequence of operations that makes your final canvas identical to the given canvas $c$. If no valid painting plan exists, output -1.

Input Format

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

The following $n$ lines each contain $m$ integers; the $j$-th integer of the $i$-th line is $c_{i,j}$ ($1\le c_{i,j}\le n\times m$), the colour of each cell.

Output Format

If there is no solution, output one line containing the integer -1.

Otherwise, output an integer $q$ ($1\le q \le n\times m$) on the first line, the number of operations.

Then output the operations in order, $q$ lines, each containing three integers $x, y, p$: the top-left corner $(x,y)$ of your chosen square ($1\le x \le n-1, 1\le y \le m-1$) and the colour $p$ that square will be painted.

If there are multiple solutions, output any of them.

Sample Input 1

4 4
5 5 3 3
1 1 5 3
2 2 5 4
2 2 4 4

Sample Output 1

6
1 3 3
3 3 4
2 2 5
1 1 5
2 1 1
3 1 2

Sample Input 2

3 4
1 1 1 1
2 2 3 1
2 2 1 1

Sample Output 2

-1

Sample Explanation

For the first input, the following is one valid painting plan:

For the second input, it is impossible to find a suitable solution.