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

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

На шахматной доске размером $$$999 \times 999$$$ расположено $$$666$$$ чёрных ладей и $$$1$$$ белый король. Задача белого короля — попасть под шах ладьи, т. е. встать на такое поле, что на одной горизонтали или вертикали с ним будет находиться чёрная ладья.

Ходы совершаются по очереди, начинают белые. NN играет за белого короля, на каждом ходу он перемещает короля в одну из соседних по стороне или диагонали клеток, т. е. если король стоит на поле $$$(x, y)$$$, то он может переместиться на поле $$$(nx, ny)$$$ такое, что $$$\max (|nx - x|, |ny - y|) = 1$$$ , $$$1 \leq nx, ny \leq 999$$$. При этом NN не имеет права брать фигуры Даши, т. е. перемещаться на поле, на котором в данный момент находится чёрная ладья. Однако он может вставать на одну горизонталь или вертикаль с черными ладьями.

А вот Даша шахматными правилами пренебрегает, и вместо обычных ходов ладьи на каждом ходу она перемещает одну из своих ладей на любое свободное поле. Также возможно, что ладья переместится на то же самое поле, на котором она стоит в данный момент, т. е. позиция останется неизменной. Однако, Даша не может поставить ладью на одну строку или на один столбец с королем.

Каждый игрок делает $$$2000$$$ ходов, если за это время белый король не попадет под шах ладьи, то победителем объявляются чёрные.

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

Чтобы сделать ход королем, выведите два целых числа $$$x$$$ и $$$y$$$ ($$$1 \leq x, y \leq 999$$$) — поле, на которое будет перемещен король. Король не имеет права вставать на поле, на котором в данный момент находится черная ладья (т. е. король не может брать ладьи). Гарантируется, что у короля в каждый момент будет возможность совершить корректный ход.

После каждого вашего хода считайте ход ладьи в следующем формате: в одной строке находятся три целых числа $$$k$$$, $$$x$$$ и $$$y$$$ ($$$1 \leq k \leq 666$$$, $$$1 \leq x_i, y_i \leq 999$$$) — номер ладьи, совершающей ход и поле, на которое ладья перемещается. Гарантируется, что ладья не будет перемещаться на поле, в котором в данный момент стоит другая ладья или король, но при этом ладья может совершить ход на поле, в котором она находилась до хода (т. е. остаться на том же поле). Гарантируется, что после хода ладьи король не будет под шахом. В случае, если ваш король попал под шах ладьи, все три числа будут равны $$$-1$$$, после чего ваша программа должна немедленно завершиться.

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

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

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

Взломы в этой задаче запрещены.