bojanje — COCI CONTEST_#3
Task type: batch | Time limit: 1 s | Memory limit: 512 MB | Difficulty: 16
Algorithms: constructive

## Task Bojanje

Marin, having become exceptionally skilled in competitive programming, decided to find a new hobby to keep himself entertained while waiting for you to catch up. While you were solving previous problems, Marin discovered a great love for painting.

He took a blank white canvas and two colors, red and blue. He began painting perfectly horizontal and vertical strokes on the canvas, from one edge to the opposite edge. The canvas can be imagined as an $n \times n$ grid, where rows and columns are numbered from 1 to $n$, and it starts completely white. Each of Marin's strokes can be imagined as choosing one of the two colors and a row or column, then coloring all the cells in that row/column with the chosen color, regardless of what was previously on the field. Marin will make a finite number of strokes and complete his painting.

However, his friend Stjepan found a painting that resembles Marin's but is unsure if it is really his. The painting he found can again be imagined as an $n \times n$ grid where each cell is white, blue, or red. The painting is *possibly Marin's* if there exists a sequence of strokes on a blank canvas, as described above, that produces an image identical to the one found. Stjepan has asked you to help him determine whether the painting might be Marin's and, if so, to find a sequence of strokes that produces the found painting.

### Input

The first line contains a positive integer $n$ ($1 \le n \le 2000$).

In the next $n$ lines, there are $n$ integers $a_{i,j}$ ($0 \le a_{i,j} \le 2$), where each represents the color in the $i$-th row and $j$-th column (0 if white, 1 if red, and 2 if blue).

### Output

If the painting is possibly Marin's, then in the first line, print the number of strokes $K$ ($0 \le K < 4000$). In the next $K$ lines, you should print three integers. The first will indicate whether the $i$-th stroke was on a row or a column (1 for a row, 2 for a column). The second number will indicate the index of the row or column where the stroke is performed, and the third number will indicate the color in the same way as described in the Input section.

If the painting is certainly not Marin's, print "-1" (without quotes) in the first and only line.

### Scoring

| Subtask | Points | Constraints                |
|---------|--------|----------------------------|
| 1       | 15     | $a_{i,j} \le 1$            |
| 2       | 35     | $n \le 100$                |
| 3       | 40     | No additional constraints. |

### Examples

| Input   | Input   | Input    |
|---------|---------|----------|
| 3       | 3       | 4        |
| 0 0 1   | 1 1 2   | 0 1 2 1  |
| 1 1 1   | 2 1 1   | 2 2 2 1  |
| 0 0 1   | 2 1 1   | 0 1 2 1  |
|         |         | 1 1 2 1  |
| Output  | Output  | Output   |
| 2       | -1      | 5        |
| 2 3 1   |         | 2 2 1    |
| 1 2 1   |         | 1 2 2    |
|         |         | 2 4 1    |
|         |         | 1 4 1    |
|         |         | 2 3 2    |

Starter code: