Problem Description

Shik the mastermind has invented a game. This game is played on a grid of size $N \times N$ (where $N$ is an even number), as shown in the figure (top-left corner is $(1,1)$, bottom-right corner is $(N,N)$):

The rules of the game are as follows:
- The initial setup is: red pieces are placed on the leftmost column and the top-left half of the top row and the bottom-left half of the bottom row, while blue pieces are placed on the rightmost column and the top-right half of the top row and the bottom-right half of the bottom row;
- Red moves first, followed by blue;
- The game ends when one side has only $N \div 2$ pieces left, and the other side wins;
- The game also ends when one side has no valid moves left, and the other side wins;
- Each move allows a piece to move one cell up, down, left, or right, but the target cell must be empty;
- A player can capture the opponent's pieces if, in a row or column, there are exactly $N-1$ pieces (or $N-2$ pieces when $N > 4$), with $N-2$ (or $N-3$ when $N > 4$) being the player's own pieces, the remaining piece(s) being the opponent's, all the player's pieces are adjacent, all the opponent's pieces are adjacent, and one of the player's pieces is adjacent to the opponent's pieces, and this situation was created by the player's own move, then the player can capture all the opponent's pieces in that row or column.

Your task is to simulate the process of the game.

The above is an example of a situation where no pieces can be captured. (Red capturing blue)

However, if the blue piece was originally at $(3,3)$ and the red piece moved from $(2,2)$ to $(2,3)$, then capturing would be possible.

If you are having trouble understanding, it is strongly recommended to manually go through the sample cases.

Input Format

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

The next $K$ lines each contain four integers $a, b, c, d$, indicating that a piece originally at $(a, b)$ moved to $(c, d)$. Starting from the second line, even-numbered lines represent blue's moves, and odd-numbered lines represent red's moves.

Output Format

Output the answer in three possible scenarios:
- If the data is invalid: output $0$.
- If the game has not ended yet: output $1$ on the first line, followed by $N$ lines, each containing $N$ characters, representing the current state of the board. Use h for red pieces, l for blue pieces, and . for empty cells. If a player can capture pieces in this state, output the state after capturing.
- If the game has ended: output $2$ on the first line, followed by red or blue on the second line, indicating which player won. The next $N$ lines should output the state of the board at the time of victory. Use h for red pieces, l for blue pieces, and . for empty cells. If a player can capture pieces in this state, output the state after capturing. Your program should ignore all input after the move that determined the winner.

Sample Input and Output

Sample Input #1

4 1
1 4 1 3

Sample Output #1

0

Sample Input #2

4 2
1 3 2 3
3 4 3 3

Sample Output #2

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

Sample Input #3

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

Sample Output #3

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

Sample Input #4

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

Sample Output #4

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

Notes/Hints

In Sample 4, when the 21st move occurred, red had already won, so the 22nd illegal move should be ignored.

For $30\%$ of the data, there are no situations where pieces can be captured;

For $60\%$ of the data, $N = 4$;

For $80\%$ of the data, $4 \le N \le 6$;

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

见题面 Input 部分

见题面 Output 部分