2157 год. Полдень человечества. Вооруженные Великой теорией Воспитания, люди забыли о войнах, голоде и терроризме. Возродилась природа. Прорыв в медицине избавил людей от болезней, позволил использовать скрытые ресурсы человеческого тела. Жители Земли осваивают отдалённые планеты, а Андрей и Илья сражаются за звание чемпиона района по шахматам.

Правила в шахматах в будущем сильно изменились. Например, игроки играют не на обычной доске, а на так называемом «Торе» – фигуры могут ходить через границы поля, переставляя свою фигуру в соответствующую клетку с другой стороны доски (подсчёт клеток, находящихся под боем фигуры, определяется аналогично). Так, например, ход короля с клетки H4 на одну вправо приведёт к появлению его в клетке A4, а ход ферзя на одну клетку по диагонали вниз и вправо из клетки E1 ведёт к появлению ферзя на клетке F8. Игра происходит на доске 8 на 8.

Ниже показан пример возможных ходов ферзя по одной из диагоналей:

Естественно, в такой формулировке привычное нам начальное положение шахмат становится бессмысленным – ведь в ней короли стоят в соседних клетках! В связи с этим правила пришлось существенно поменять до такой степени, что в какой-то момент у игрока может вообще не остаться короля!

Так и случилось с белыми фигурами. На текущий момент белые фигуры имеют только лишь двух ферзей, тогда как у чёрных остался один король. В шахматах будущего всё же есть что-то общее с нашими, хотя бы потому что фигуры ходят точно так же: например, ферзь ходит на любое количество клеток по вертикали, горизонтали и диагонали, а король на одну клетку в любую сторону.

Правила шахмат таковы, что единственный шанс выиграть у белых – поставить мат чёрному королю в привычном нам смысле, то есть создать такую ситуацию, когда все перемещения чёрного короля ведут к шаху, и при этом в данный момент король находится под шахом. Единственный шанс выиграть чёрному королю – съесть все фигуры соперника.

Есть также вариант ничьей – например, если чёрный король попал в ситуацию, когда ему некуда ходить в свой ход, но под боем он не находится. Также если игра не закончится за 7 ходов, будет объявлена ничья.

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

Вы играете за белых и делаете первый ход. Каждый ваш ход должен описываться единственной строкой, содержащей три числа, разделённых пробелом. Первое число – номер ферзя, который должен сейчас походить (ферзи пронумерованы во входных данных). Затем должны идти два числа, каждое из которых не превосходит 7 по модулю – смещение соответствующего ферзя по первой и второй координате соответственно. Смещения не должны быть одновременно равны нулю и должны быть корректным ходом ферзя.

Программа жюри в ответ выдаст вам два числа в отдельной строке разделённые единственным пробелом, каждое не превосходит по модулю 1 – смещение короля по каждой координате соответственно. Гарантируется, что король и в случае шаха, если это возможно, уходит от него.

Возможны исключительные случаи.

Во-первых, вы можете поставить мат чёрному королю. В таком случае следует в отдельной строке вывести слово «Checkmate!» без кавычек, и после этого завершить работу программы.

Во-вторых, вы можете случайно нарушить какие-нибудь правила. Например, сделать более 7 ходов, поставить чёрного короля в пат, забыть вывести слово «Checkmate!» в конце или даже сделать какой-нибудь некорректный ход(попытаться походить ферзём как конём или поставить ферзя в уже занятую другим ферзём клетку). Во всех этих случаях вы получите на вход строку, состоящую из двух нулей, разделённых пробелом. После этого вам необходимо завершить работу программы. Также вы получите эту строку, если потеряете хотя бы одного ферзя или выведите неправильный номер ферзя (не равный 1 или 2).

После каждого действия вашей программы выводите символ перевода строки. После вывода очередной строки обязательно используйте функции очистки потока, чтобы часть вашего вывода не осталась в каком-нибудь буфере. Например, на С++ надо использовать функцию «fflush(stdout)», на Java и Kotlin вызов «System.out.flush()» и «stdout.flush()» для языка Python.