Knightmare (hard)
Contest: Codeforces Round 577 (Div. 2)
Difficulty rating: 3000
Tags: graphs, interactive, shortest paths

This is an interactive problem.

Alice and Bob are playing a game on the chessboard of size $$$n \times m$$$ where $$$n$$$ and $$$m$$$ are even. The rows are numbered from $$$1$$$ to $$$n$$$ and the columns are numbered from $$$1$$$ to $$$m$$$. There are two knights on the chessboard. A white one initially is on the position $$$(x_1, y_1)$$$, while the black one is on the position $$$(x_2, y_2)$$$. Alice will choose one of the knights to play with, and Bob will use the other one.

The Alice and Bob will play in turns and whoever controls the white knight starts the game. During a turn, the player must move their knight adhering the chess rules. That is, if the knight is currently on the position $$$(x, y)$$$, it can be moved to any of those positions (as long as they are inside the chessboard):

$$$(x+1, y+2)$$$, $$$(x+1, y-2)$$$, $$$(x-1, y+2)$$$, $$$(x-1, y-2)$$$,$$$(x+2, y+1)$$$, $$$(x+2, y-1)$$$, $$$(x-2, y+1)$$$, $$$(x-2, y-1)$$$.

We all know that knights are strongest in the middle of the board. Both knight have a single position they want to reach:

- the owner of the white knight wins if it captures the black knight or if the white knight is at $$$(n/2, m/2)$$$ and this position is not under attack of the black knight at this moment;
- The owner of the black knight wins if it captures the white knight or if the black knight is at $$$(n/2+1, m/2)$$$ and this position is not under attack of the white knight at this moment.

Formally, the player who captures the other knight wins. The player who is at its target square ($$$(n/2, m/2)$$$ for white, $$$(n/2+1, m/2)$$$ for black) and this position is not under opponent's attack, also wins.

A position is under attack of a knight if it can move into this position. Capturing a knight means that a player moves their knight to the cell where the opponent's knight is.

If Alice made $$$350$$$ moves and nobody won, the game is a draw.

Alice is unsure in her chess skills, so she asks you for a help. Choose a knight and win the game for her. It can be shown, that Alice always has a winning strategy.

Interaction format:
The interaction starts with two integers $$$n$$$ and $$$m$$$ ($$$6 \le n,m \le 1000$$$, $$$n$$$ and $$$m$$$ are even) — the dimensions of the chessboard.

The second line contains four integers $$$x_1, y_1, x_2, y_2$$$ ($$$1 \le x_1, x_2 \le n$$$, $$$1 \le y_1, y_2 \le m$$$) — the positions of the white and the black knight. It is guaranteed that the two knights have different starting positions. It is also guaranteed that none of the knights are in their own target square in the beginning of the game (however, they can be on the opponent's target position).

Your program should reply with either "WHITE" or "BLACK", depending on the knight you want to play with. In case you select the white knight, you start the game.

During every your turn, you need to print two integers: $$$x$$$ and $$$y$$$, the position to move the knight. If you won the game by this turn, you must terminate your program immediately.

After every turn of the opponent, you will receive two integers: $$$x$$$ and $$$y$$$, the position where Bob moved his knight.

If your last move was illegal or you lost the game after jury's turn, or you made $$$350$$$ moves, and haven't won, you will receive "-1 -1". In such cases, you should terminate your program and then you will get a Wrong Answer verdict.

After printing anything, do not forget to output the end of line and flush the output. Otherwise, you might get Idleness limit exceeded. To do this, use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see documentation for other languages.

Hacks are disabled for this problem.

Jury's program is adaptive: the moves of jury may depend on the moves made by your program.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first example, the white knight can reach it's target square in one move.

In the second example black knight wins, no matter what white knight moves.

Example input:
8 8
2 3 1 8

Example output:
WHITE
4 4

Example input:
6 6
4 4 2 2
6 3

Example output:
BLACK
4 3

Editorial:
First calculate the number of moves needed to reach (without capturing) positions $$$(a_1;b_1)$$$ and $$$(a_2;b_2)$$$.
If one of the knights can reach it's goal at least 2 moves faster than the other can and faster than the other can reach it's goal, than there is a winning strategy with it. Just go the shortest path. The other knight won't be able to capture your knight, because after you move you are $$$x$$$ moves away from it, than the other knight must be at least $$$x+2$$$ far, so it will be at least $$$x+1$$$ after it's move.
If one of the knights can reach it's goal at exactly 1 move faster than the other can and faster than the other can reach it's goal, we have to count the moves needed to reach all the positions which is 1 move away from the goal. If there is a position from these which can be reached at least 2 moves faster, than that knight can win.
Let's color the chessboard the regular way with white and black colors. If the 2 knights are in same color, than only the black knight can capture the white, otherwise only the white can capture the black (that is because knights always move to different color than they come from).
In all the other situation there is at least drawing strategy with the knight that can capture the other:
Move to the position that the other knight have to reach and stay there or 1 move away from it. The other knight won't be able to reach that position without getting captured. So we choose that knight and search for the winning strategy. You can win the game in 2 steps:
First: Go to your opponent's target cell in the fastest way (if the opponent could go there faster, you can still outrun him, because there is no position which is 1 move away from the opponents goal and can be reached at least 2 moves faster (we already looked that situation), so you can take away the opponent's possibility to reach the target by threatening with capturing their knight). This is maximum of 333 moves.
Second: Go from there to your target cell on the fastest way. It can be easily shown that it takes 3 moves to go there. When you are in the opponent's target position your opponent can be either exactly 1 move or at least 3 moves away from you (because the distance (in moves) between you and your opponent's knight after your opponent's turn is always odd). If it is 1 move away, you can capture his knight, if at least 3 or moves away from you (and therefore the target position), you can reach your target faster than your opponent.
That's a total of 336 moves.