Big Brush solution codeforces- You found a painting on a canvas of size n×mn×m. The canvas can be represented as a grid with nn rows and mm columns. Each cell has some color. Cell (i,j)(i,j) has color ci,jci,j.

Big Brush solution codeforces

You found a painting on a canvas of size n×mn×m. The canvas can be represented as a grid with nn rows and mm columns. Each cell has some color. Cell (i,j)(i,j) has color ci,jci,j.

Near the painting you also found a brush in the shape of a 2×22×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 ii and jj (1i<n1≤i<n1j<m1≤j<m) and some color kk (1knm1≤k≤nm).
  • Paint cells (i,j)(i,j)(i+1,j)(i+1,j)(i,j+1)(i,j+1)(i+1,j+1)(i+1,j+1) in color kk.

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 nmnm operations that could have led to the painting you found or state that it’s impossible.

Input

Big Brush solution codeforces

The first line of input contains two integers nn and mm (2n,m10002≤n,m≤1000) — the dimensions of the canvas.

On the ii-th of the next nn lines of input, there will be mm integers. The jj-th of them is ai,jai,j (1ai,jnm1≤ai,j≤nm) — the color of cell (i,j)(i,j).

Output

Big Brush solution codeforces

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

Otherwise, on the first line, print one integer qq (1qnm1≤q≤nm) — the number of operations.

Next, print the operations in order. On the kk-th of the next qq lines, print three integers iijjcc (1i<n1≤i<n1j<m1≤j<m1cnm1≤c≤nm) — the description of the kk-th operation.

If there are multiple solutions, print any.

Big Brush solution codeforces

input

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

output

Big Brush solution codeforces

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

input

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

output

Copy
-1
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−1.

Leave a Comment

Your email address will not be published.