E2. Ночной шахмар (сложная)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

Алиса и Боб играют в игру на шахматной доске размера $$$n \times m$$$, где $$$n$$$ и $$$m$$$ являются чётными числами. Ряды доски пронумерованы целыми числами от $$$1$$$ до $$$n$$$, а столбцы пронумерованы от $$$1$$$ до $$$m$$$. На доске расположены два коня — белый и чёрный. Белый изначально находится в клетке $$$(x_1, y_1)$$$, а чёрный — в клетке $$$(x_2, y_2)$$$. Алиса выбирает коня, которым будет играть сама, а Боб будет играть другим.

Алиса и Боб будут делать ходы по очереди. Тот, кто играет белым конём, начинает игру. За один ход каждый игрок должен передвинуть своего коня в соответствии с шахматными правилами. А именно, если сейчас конь находится в клетке $$$(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)$$$ для чёрного коня) не под боем оппонента, выигрывает.

Клетка находится под боем другого коня, если тот может сходить в эту клетку. Взятие коня означает, что игрок перемещает своего коня в клетку, где расположен конь соперника.

Если Алиса сделала $$$350$$$ ходов и никто не выиграл, игра заканчивается вничью.

Алиса не уверена в своих шахматных способностях, так что она попросила у вас помощи. Выберите коня и выиграйте игру за неё. Можно показать, что у Алисы всегда есть выигрышная стратегия.

Протокол взаимодействия

Взаимодействие начинается с двух целых чисел $$$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$$$ — координаты клетки, в которую вы хотите переместить своего коня. Если вы выиграли игру этим ходом, вы должны немедленно завершить свою программу.

После каждого хода оппонента вы получите два целых числа: $$$x$$$ и $$$y$$$ — координаты клетки, куда Боб переместил своего коня.

Если ваш последний ход был некорректен или вы проиграли игру в результате хода программы жюри, или если вы сделали $$$350$$$ ходов и всё ещё не выиграли, вы получите «-1 -1». В таких случаях, немедленно завершите вашу программу, чтобы получить вердикт Неправильный ответ.

После того, как вы что-то вывели, не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.

Взломы в этой задаче отключены.

Программа жюри является адаптивной: ходы жюри могут зависеть от ходов, которые сделает ваша программа.

Примеры
Входные данные
8 8
2 3 1 8
Выходные данные
WHITE
4 4
Входные данные
6 6
4 4 2 2
6 3
Выходные данные
BLACK
4 3
Примечание

В первом примере белый конь может достигнуть своей конечной клетки за один ход.

Во втором примере чёрный конь выигрывает вне зависимости от того, что делает белый конь.