Description
There is a pawn on a chessboard that needs to reach the bottom row. The rule for the pawn's movement is that it can move one square to the left, one square to the right, or one square forward. At the same time, there are two pieces belonging to the other side on the board that need to intercept this pawn from reaching the bottom row. The movement of these two pieces is the same as a "General" (in Chinese chess), meaning they can move to any adjacent square in the four directions: front, back, left, and right. Therefore, this problem can be called "General Intercepts the Crossing Pawn."
There is an $n \times m$ chessboard. We use $(i, j)$ to denote the position at the $i$-th row and $j$-th column. There are some obstacles on the board, as well as one black piece and two red pieces.
The rules of the game are as follows: Red moves first, Black moves second, and both sides take turns moving. In each turn, Red can choose one of their red pieces and move it one square to an adjacent position on the board. Specifically, if the chosen red piece is at $(i, j)$, it can move to one of $(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)$, provided the destination is within the board, contains no obstacles, and is not occupied by the other red piece.
In each turn, Black can move their piece one square in one of three directions. Specifically, if the black piece is at $(i, j)$, it can move to one of $(i - 1, j), (i, j - 1), (i, j + 1)$, provided the destination is within the board and contains no obstacles.
Before a player makes a move, if any of the following conditions occur, the game ends immediately, and the winner is determined according to the following rules (in order of priority): The black piece is in the first row. In this case, Black wins. The black piece and one of the red pieces are at the same position. In this case, the player who made the previous move wins. * The current player cannot make any legal moves. In this case, the opponent wins.
Assume both sides play with an optimal strategy and will not make moves that are disadvantageous to themselves. That is: If a winning strategy exists, the player will choose the move that minimizes the maximum number of steps required for them to win, regardless of how the opponent plays. If no winning strategy exists, but there is a strategy that prevents losing regardless of how the opponent acts, the player will choose any non-losing strategy. * If no non-losing strategy exists, the player will choose the move that maximizes the minimum number of steps required for the opponent to win, regardless of how the opponent plays.
If the game does not end after $100^{100^{100}}$ turns, it is considered a draw. Determine the total number of moves made by both sides when the game ends, or determine if it is a draw.
Input
The input is read from the file zu.in.
There are multiple test cases.
The first line contains two integers id and T, representing the test point ID and the number of test cases, respectively. Specifically, the ID for the sample is 0.
Each of the following $T$ test cases is formatted as follows:
The first line contains two positive integers $n$ and $m$, representing the number of rows and columns of the chessboard.
The next $n$ lines each contain a string of length $m$, where the $j$-th character of the $i$-th line represents the state of the position $(i, j)$ on the board.
In these characters: '.' represents an empty space; '#' represents an obstacle; 'X' represents the black piece; 'O' represents a red piece.
It is guaranteed that there is exactly one black piece, exactly two red pieces, and the black piece is not in the first row.
Output
Output to the file zu.out.
For each test case, output a single line of string.
If the game is a draw, output "Tie".
If Red wins, output "Red t", where $t$ is the total number of moves made by both sides when the game ends. This should obviously be an odd number.
If Black wins, output "Black t", where $t$ is the total number of moves made by both sides when the game ends. This should obviously be an even number.
Note: Output the string inside the double quotes, excluding the quotes themselves.
Examples
Input 1
0 5 4 5 ...#O .#..# #O#.. .#..X 3 3 #.# O.O .X. 3 3 O.. .#X .O. 5 5 ..... ..... ..O.. #..#. O#.X. 9 9 ...###### .#....... .#######. .#.#..... .#O#.#### .#.#..... .#######. .#X...... .O.......
Output 1
Black 0 Black 2 Black 2 Tie Red 75
Note
For the first test case, Red has no valid moves on the first turn, so Black wins. For the second test case, no matter how Red moves on the first turn, Black can make the black piece and a red piece occupy the same position on the next turn. For the third test case, no matter how Red moves on the first turn, Black can move their piece one square up to achieve victory. For the fourth test case, one red piece cannot move. The other red piece can move in the third row to prevent the black piece from entering the first row. The black piece can also keep moving in the fifth row. If the red piece reaches the fifth row, the black piece can choose to escape from the other side. For the fifth test case, the red piece in the last row can go around from the left to capture the black piece. Note that the other red piece can also move.
Subtasks
For all data, it is guaranteed that: $1 \le T \le 10$; $2 \le n \le 10$; $1 \le m \le 10$; id equals the test point number.
For each test case, it is guaranteed that there is exactly one black piece, exactly two red pieces, and the black piece is not in the first row.
- Test points 1 ~ 4: Guaranteed to be either a draw or Red cannot move at the start.
- Test points 5 ~ 6: Guaranteed $n \ge 4$. Guaranteed that every square in the $(n-1)$-th row is an obstacle, and there are no other obstacles on the board. Guaranteed the black piece is in the first $n-2$ rows, one red piece is in the first $n-2$ rows, and the other red piece is in the $n$-th row.
- Test points 7 ~ 9: Guaranteed $m = 1$.
- Test points 10 ~ 13: Guaranteed to be either a draw or there exists a strategy to end the game within 9 moves.
- Test points 14 ~ 20: No special restrictions.