On a $10$ row by $9$ column chessboard, a game called "Qi Men Xiang Qi" is being played. Each side has several pieces, and different pieces have different characteristics. We use the $(x, y)$ coordinates to represent the position in the $x$-th row and the $y$-th column of the chessboard.
Our side has several Rooks and several Knights, as well as the skill Shape-shifting. The movement methods of these two types of pieces and the skill are described as follows:
- Suppose the Rook is located at coordinates $(a, b)$. If it moves to coordinates $(c, d)$ on the chessboard in one action, the following conditions must be met:
- There are no friendly pieces at $(c, d)$. That is, it cannot capture friendly pieces, nor can it overlap with friendly pieces.
- $c = a$ or $d = b$, but $(a, b) \neq (c, d)$. That is, it can move along the row or column it is in, but cannot remain in the same position.
- There cannot be any other pieces between $(a, b)$ and $(c, d)$. That is, it cannot jump over other pieces while moving.
- Suppose the Knight is located at coordinates $(a, b)$. If it moves to coordinates $(c, d)$ on the chessboard in one action, the following conditions must be met:
- There are no friendly pieces at $(c, d)$. That is, it cannot capture friendly pieces, nor can it overlap with friendly pieces.
- $\{|a - c|, |b - d|\} = \{1, 2\}$. Here, $\{\dots\}$ denotes an unordered set. This corresponds to the traditional chess movement of the "L" shape (note that there are no "knight traps" in this problem).
- Shape-shifting: This can be used as one action to swap the positions of any two friendly pieces. There is no limit on the number of uses.
The enemy has several Slimes. Slimes cannot move but have the following characteristics:
- Suppose the Slime is located at coordinates $(a, b)$. When it is captured and removed, it will immediately split, generating one Slime in each of the four adjacent positions (up, down, left, right). Specifically, in these four adjacent positions, no new slimes will be generated in positions that already have any other pieces or are out of bounds of the chessboard.
- The Slimes generated by splitting have the same splitting characteristics and there is no limit on the number of splits.
After moving the pieces, if they overlap with enemy pieces, it triggers a capture, removing the enemy pieces. The victory condition of the game is to capture all enemy Slimes, ensuring that there are no enemy pieces left on the chessboard.
While playing the game, Xiao Biao found that although the enemy cannot move their pieces, it is still difficult for our side to cleanly capture the Slimes, as they are numerous and split very efficiently, often leading to more slimes being generated, making it hard for Xiao Biao to determine if victory is possible in this game. He has come to you, who are skilled in strategy and analysis, hoping you can help him determine if there exists a strategy to achieve victory within $10^4$ moves. If such a winning strategy exists, please output the operations for each step.
Input
The input consists of $10$ lines, each containing a string of length $9$, representing the chessboard situation. Where the character . represents an empty position; the character C represents our Rook; the character M represents our Knight; and the character S represents the enemy Slime.
Each type of character may appear multiple times. The data guarantees that there is at least one Slime on the chessboard and at least one friendly piece.
Output
If there is no strategy to win within $10^4$ moves:
- Please output a single line string
WuJie.
If there exists a strategy to win within $10^4$ moves:
- First, output a single line string
YouJie. - Next, output an integer $s$, representing the number of actions.
- Then, output $s$ lines, each containing four integers $a, b, c, d$, indicating that the friendly piece currently at $(a, b)$ is moved to position $(c, d)$. Specifically, if both positions $(a, b)$ and $(c, d)$ already have friendly pieces, this action is considered Shape-shifting, indicating that these two pieces swap positions.
- Your strategy must ensure that after all actions are completed, there are no Slimes remaining on the chessboard.
If there are multiple different valid solutions, any one of them can be output.
Solutions that do not meet the format requirements, do not comply with the piece movement rules, or indicate that there is no piece at position $(a, b)$ will be considered incorrect.
Examples
Input 1
...CSC... ...CCCM.. ......... ......... ......... ......... ......... ......... ......... .........
Output 1
YouJie 6 1 4 1 3 1 3 1 2 1 2 1 1 1 1 2 4 2 4 1 4 2 7 1 5
Input 2
SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSCSSSS
Output 2
WuJie
Note
The output for sample $1$ demonstrates multiple valid operations, and ultimately captures all slimes.
- Steps $1$ to $3$ show the Rook at $(1, 4)$ moving left, choosing to move one square at a time, and finally landing at $(1, 1)$.
- Step $4$ demonstrates the Shape-shifting operation, swapping the Rook at $(1, 1)$ with the Rook at $(2, 4)$.
- Step $5$ shows the Rook at $(2, 4)$ moving up to $(1, 4)$.
- The final step shows the Knight jumping from $(2, 7)$ to $(1, 5)$ to capture the only Slime. Since there are no valid empty positions adjacent to the Slime after this, it cannot split. The game is won.