Problem Description

Expert Shik invented a game. The game is played on an $N \times N$ grid (where $N$ is even), as shown in the figure (top-left is $(1,1)$, bottom-right is $(N,N)$):

The rules are as follows:

• Initial position: Red pieces are placed on all cells in the leftmost column, and Blue pieces are placed on all cells in the rightmost column. In addition, on the top row and the bottom row, Red pieces are placed on the left half, and Blue pieces are placed on the right half.
• Red moves first, Blue moves second.
• When one side has only $N\div 2$ pieces left, the game ends and the other side wins.
• When one side has no legal move, the game ends and the other side wins.
• Each move: move one piece by $1$ cell in one of the four directions (up, down, left, right), and the destination cell must be empty.
• Capturing is allowed when all of the following are satisfied: in a single row (or a single column), there are exactly $N-1$ pieces (when $N>4$, having $N-2$ pieces is also allowed). Among them, $N-2$ are your own pieces (when $N>4$, having $N-3$ is also allowed), and the remaining $1$ piece (when $N>4$, having $2$ pieces is also allowed) belongs to the opponent. All of your pieces are consecutive, all opponent pieces are consecutive, and at least one of your pieces is adjacent to an opponent piece. Moreover, this position must be formed by your active move. Then you may capture (remove) all opponent pieces in that row/column.

Now, please simulate the game process.

The position above is one where capturing is not allowed. (Red captures Blue.)

But if the Blue piece was originally at $(3,3)$, and the Red piece moves from $(2,2)$ to $(2,3)$, then capturing is allowed.

If you cannot understand this, it is strongly recommended that you manually work through the sample once.

Input Format

The first line of the input contains two integers $N$ and $K$, representing the board size and the total number of moves.

The next $K$ lines each contain four integers $a,b,c,d$, meaning that a piece originally at $(a,b)$ moves to $(c,d)$. Counting from the second line of the file, even-numbered lines represent Blue, and odd-numbered lines represent Red.

Output Format

Output the answer in three cases:

• Invalid testdata: output $0$.
• The game has not ended yet: output $1$ on the first line. Then output $N$ lines, each with $N$ characters, representing the current board. Use h for a Red piece, l for a Blue piece, and . for an empty cell. If in this position one side can capture, output the state after capturing.
• The game has ended: output $2$ on the first line. Output red or blue on the second line to indicate the winner. From the third line to line $N+2$, output the board position when the winner is determined. Use h for a Red piece, l for a Blue piece, and . for an empty cell. If in this position one side can capture, output the state after capturing. Your program should ignore all remaining input after the move that allows you to determine the winner.

4 1
1 4 1 3

0

4 2
1 3 2 3
3 4 3 3

1
hhll
h..l
..ll
hh.l

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

1
.hhh..
h..l.l
.h...l
h....l
h....l
hhhlll

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

2
red
...h..
hhh...
.h...l
h...l.
h..l..
.hhh..

Hint

Explanation for Sample 4: at move 21, Red has already won, so the illegal move at move 22 should be ignored.

For $30\%$ of the testdata, there is no capturing.

For $60\%$ of the testdata, $N=4$.

For $80\%$ of the testdata, $4\le N\le 6$.

For $100\%$ of the testdata, $4\le N\le 10$, $1 \le K \le 10^3$.

Translated by ChatGPT 5