Description

Mayan puzzle is a recently popular game. The game interface is a $7$-row $\times 5$-column board stacked with some blocks. Blocks cannot be suspended in the air, i.e., a block must be placed on the bottom row or on top of another block. To clear the game means to eliminate all blocks within a given number of moves. The elimination rules are as follows:

1. In each move, you may and only may drag one block horizontally (left or right) by one cell: When dragging this block, if the target position also has a block, the two blocks will swap positions (see Figures $6$ to $7$ in the sample I/O explanation). If the target position is empty, the dragged block will be pulled out of its original column and will fall from the target position (until it is supported; see Figures $1$ and $2$ below).

2. At any time, if there are three or more consecutive blocks of the same color in any row or column, they will be eliminated immediately (see Figures 1 to 3).

Notes: a) If multiple groups of blocks simultaneously satisfy the elimination condition, all such groups will be eliminated at the same time (for example, in Figure $4$, three blocks of color $1$ and three blocks of color $2$ are eliminated simultaneously, leaving one block of color $2$). b) When both a row and a column satisfy the elimination condition and they share a block, all blocks in that row and column that satisfy the condition will be eliminated simultaneously (for example, in the situation shown in Figure 5, $5$ blocks are eliminated at the same time).

3. After blocks are eliminated, the blocks above the eliminated positions will fall, and the falling may trigger new eliminations. Note: No elimination occurs during the falling process.

Figures $1$ to $3$ above show the changes on the board after moving a block. The coordinates of the block in the lower-left corner of the board are $(0,0)$. After moving the block at $(3,3)$ to the left, the interface changes from Figure $1$ to the state shown in Figure $2$. At this time there are three consecutive blocks of color $4$ in one column, satisfying the elimination condition. After eliminating the three consecutive blocks of color $4$, the blocks of color $3$ above fall, forming the situation shown in Figure $3$.

Input Format

A total of $6$ lines.

• The first line is a positive integer $n$, the number of moves required to clear the game.
• The next $5$ lines describe the $7 \times 5$ game interface. Each line contains several integers separated by a space and ends with a $0$. For each column (from left to right), the integers list the color numbers of the blocks from bottom to top. There are at most $10$ colors, numbered in order starting from $1$, and the same number indicates the same color.
• The testdata guarantees that there are no eliminable blocks on the initial board.

Output Format

If there is a solution, output $n$ lines, each containing $3$ integers $x, y, g$ separated by a space, representing one move. Here $(x, y)$ is the coordinate of the block to move, and $g$ is the direction: $1$ means move to the right, $-1$ means move to the left. Note: If there are multiple solutions, use $x$ as the primary key, $y$ as the secondary key, and prefer $1$ over $-1$, and output the lexicographically smallest solution. The coordinate of the lower-left corner of the board is $(0, 0)$.

If there is no solution, output a single line -1.

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

2 1 1
3 1 1
3 0 1

Hint

【Sample I/O Explanation】

In the direction of the arrows, these are Figures $6$ to $11$ in order.

The game state of the sample input is shown in the first image above. The three moves in order are: move the block at $(2,1)$ to the right, move the block at $(3,1)$ to the right, and move the block at $(3,0)$ to the right. In the end, all blocks on the board can be eliminated.

【Constraints】

• For $30\%$ of the testdata, all blocks on the initial board are on the bottom row.
• For $100\%$ of the testdata, $0 < n \le 5$.

Translated by ChatGPT 5