Output Format

Output a complete tiling plan: each placement (one line) is $x\ y\ c$ ($x, y$ are the row and column of the carpet’s corner cell, and $c$ is the carpet’s shape; see Figure $1$ above. The four shapes are represented by $1, 2, 3, 4$. Separate $x, y, c$ with a single space).

3                          
3 3   

5 5 1
2 2 4
1 1 4
1 4 3
4 1 2
4 4 1
2 7 3
1 5 4
1 8 3
3 6 3
4 8 1
7 2 2
5 1 4
6 3 2
8 1 2
8 4 1
7 7 1
6 6 1
5 8 3
8 5 2
8 8 1

Hint

Explanation of SPJ error codes:

1. $c$ is out of range.
2. $x, y$ are out of range.
3. The position $(x, y)$ has already been covered.
4. The position $(x, y)$ was never covered.

$\text{upd 2023.8.19}$: Added sample explanation.

Sample Explanation

Translated by ChatGPT 5