Это интерактивная задача.
Алиса и Боб играют в игру. Есть доска \(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\)-м ходу игры.
Интерактор может отклониться от заданного во взломе порядка цветов, но только в том случае, если это заставит Боба проиграть.
Примечание
Конечное состояние доски из примера изображено ниже. Боб выигрывает, потому что нет двух соседних ячеек с фишками одного и того же цвета. \(\)\begin{matrix}2&3\\3&1\end{matrix}\(\)
Пример приведен только для демонстрации входного и выходного формата. Не гарантируется, что он будет представлять оптимальную стратегию для Боба или реальное поведение интерактора.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1
2
1
3
|
2 1 1
3 1 2
3 2 1
1 2 2
|