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

Алиса и Боб играют в игру. Есть доска $$$n\times n$$$, изначально пустая. Мы будем обозначать ячейку в строке $$$i$$$ и столбце $$$j$$$ как $$$(i, j)$$$ для $$$1\le i, j\le n$$$. Также, есть бесконечный запас фишек $$$3$$$ цветов, обозначенных $$$1$$$, $$$2$$$ и $$$3$$$.

Алиса и Боб ходят по очереди по следующим правилам: каждый ход начинается с того, что Алиса называет один из трех цветов, назовем его $$$a$$$. Затем Боб выбирает цвет $$$b\ne a$$$, выбирает пустую ячейку и помещает на нее фишку цвета $$$b$$$.

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

Если в какой-то момент возникает конфликт, Алиса побеждает. В противном случае, если было совершено $$$n^2$$$ ходов (так что доска полностью заполнилась) без конфликтов, побеждает Боб.

У нас есть доказательство того, что у Боба есть выигрышная стратегия. Сыграйте в игру за Боба и выиграйте.

Интерактор адаптивен. Таким образом, выбор цвета Алисой может зависеть от предыдущих ходов Боба.

Взаимодействие начинается с чтения единственного целого числа $$$n$$$ ($$$2\le n\le 100$$$) — размера доски.

Дальше начинаются ходы. Каждый ход следует начинать с чтения целого $$$a$$$ ($$$1\le a\le 3$$$) — выбранного цвета Алисы.

Затем необходимо вывести три целых числа $$$b,i,j$$$ ($$$1\le b\le 3,b\ne a, 1\le i,j\le n$$$) —, что означает, что Боб кладет в ячейку $$$(i, j)$$$ фишку цвета $$$b$$$. Ячейка $$$(i, j)$$$ не должна содержать фишки из предыдущих ходов. Если ваш ход недействителен или проигрывает партию, взаимодействие прекратится и вы получите вердикт Неправильный ответ.

После того как все $$$n^2$$$ ходов были сделаны, завершите программу, чтобы избежать неожиданных вердиктов.

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

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

Формат взломов

Для взлома используйте следующий формат.

Первая строка содержит одно целое число $$$n$$$ ($$$2\le n\le 100$$$).

Вторая строка содержит $$$n^2$$$ целых чисел $$$a_1,\ldots,a_{n^2}$$$ ($$$1\le a_i\le 3$$$), где $$$a_i$$$ обозначает цвет Алисы на $$$i$$$-м ходу игры.

Интерактор может отклониться от заданного во взломе порядка цветов, но только в том случае, если это заставит Боба проиграть.