Это интерактивная задача.
Алиса и Боб играют в игру на шахматной доске размера \(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;
- смотрите документацию для других языков.
Взломы в этой задаче отключены.
Программа жюри является адаптивной: ходы жюри могут зависеть от ходов, которые сделает ваша программа.