CF1201E2.Knightmare (hard)

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

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.

这是一个交互式问题。

Alice 和 Bob 在一个 $n \times m$ 大小的棋盘上进行游戏，其中 $n$ 和 $m$ 均为偶数。行编号从 $1$ 到 $n$，列编号从 $1$ 到 $m$。棋盘上有两个骑士：白方骑士初始位于 $(x_1, y_1)$，黑方骑士初始位于 $(x_2, y_2)$。Alice 将选择其中一个骑士进行操作，Bob 则使用另一个骑士。

Alice 和 Bob 轮流行动，且控制白方骑士的一方先行。在每一轮中，玩家必须按国际象棋规则移动自己所控制的骑士。即：若骑士当前位于 $(x, y)$，则它可以移动至以下任一位置（前提是该位置仍在棋盘范围内）：

$(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)$。

众所周知，骑士在棋盘中央时威力最强。每个骑士都有一个各自希望抵达的目标位置：

• 白方骑士的控制者获胜条件为：吃掉黑方骑士，或白方骑士到达 $(n/2, m/2)$ 且此时该位置未被黑方骑士攻击；
• 黑方骑士的控制者获胜条件为：吃掉白方骑士，或黑方骑士到达 $(n/2+1, m/2)$ 且此时该位置未被白方骑士攻击。

形式化地讲：

• 吃掉对方骑士（即某玩家将其骑士移动至对方骑士所在格子）的一方获胜；
• 某玩家将其骑士移动至其目标格（白方目标为 $(n/2, m/2)$，黑方目标为 $(n/2+1, m/2)$），且该格子此刻未被对方骑士攻击，该玩家也获胜。

一个位置被某骑士“攻击”，当且仅当该骑士可一步移动至该位置。“吃掉”骑士即指将己方骑士移动到对方骑士当前所在的格子。

若 Alice 进行了 $350$ 步而无人获胜，则游戏判为平局。

Alice 对自己的棋艺缺乏信心，因此请你协助她。请选择一个骑士，并代表 Alice 获胜。可以证明：Alice 总存在必胜策略。

交互流程

交互开始时，输入两个整数 $n$ 和 $m$（$6 \le n,m \le 1000$，且 $n$、$m$ 均为偶数）——表示棋盘尺寸。

第二行包含四个整数 $x_1, y_1, x_2, y_2$（$1 \le x_1, x_2 \le n$，$1 \le y_1, y_2 \le m$）——分别表示白方骑士与黑方骑士的初始位置。保证两骑士起始位置不同；还保证游戏开始时，没有任何骑士位于自身的目标格（但可能位于对方的目标格）。

你的程序应输出 "WHITE" 或 "BLACK"，表示你选择操作的骑士。若你选择白方骑士，则由你先手。

在你的每一轮行动中，需输出两个整数 $x$ 和 $y$，表示你将骑士移动至的位置。若你在此步获胜，则必须立即终止程序。

在对手（Bob）每轮行动后，你将收到两个整数 $x$ 和 $y$，表示 Bob 将其骑士移动到了该位置。

若你最后一步非法，或在评测员（jury）行动后你失败，或你已执行 $350$ 步却仍未获胜，则你会收到 -1 -1。此时你应立即终止程序，否则将获得 Wrong Answer 判定。

每次输出后，请务必输出换行符并刷新输出缓冲区。否则你可能会收到 Idleness limit exceeded 错误。具体方法如下：

• C++ 中使用 fflush(stdout) 或 cout.flush()；
• Java 中使用 System.out.flush()；
• Pascal 中使用 flush(output)；
• Python 中使用 stdout.flush()；
• 其他语言请查阅相应文档。

本题禁止 hack。

评测员程序是自适应的：其后续移动可能依赖于你程序所做出的移动。

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.

在第一个例子中，白方骑士可以在一步内到达目标格子。

在第二个例子中，黑方骑士必胜，无论白方骑士如何移动。