H. Не больше двух подряд
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

Напишите программу, играющую против программы жюри. Ваша программа должна выиграть все раунды. Это всегда возможно, поскольку вы сами выбираете, кто делает первый ход.

Протокол взаимодействия

Вначале прочитайте целое число $$$n$$$ ($$$1 \le n \le 30$$$) — длину полоски.

Далее решите, кто будет делать первый ход. Выведите 1, если вы ходите первым, иначе выведите 2. Затем выведите перевод строки и выполните сброс буфера в стандартный поток.

Далее ваша программа должна в цикле делать следующее.

  • Если сейчас ваш ход, то выведите одно целое число от $$$1$$$ до $$$n$$$ — номер клетки, куда вы ставите крестик. Затем выведите перевод строки и выполните сброс буфера в стандартный поток. Если ходить некуда, то выведите 0 и завершите программу.
  • Если сейчас ход противника, то прочитайте целое число от $$$0$$$ до $$$n$$$. Если введённое число больше нуля, то это номер клетки, куда сходил противник. Если введённое число равно 0, то игра окончена — завершите программу.

Пример ввода-вывода:

ВводВывод
4
1
4
2
1
0

Примечание

Для сброса буфера используйте:

  • cout.flush(); или cout << flush; или cout << endl; — для языка C++ (в последнем варианте также выведется перевод строки)
  • fflush(stdout); — для языка C (или при выводе в старом стиле на C++)
  • sys.stdout.flush() — для языка Python (нужно импортировать модуль sys)
  • System.out.flush(); — для языка Java
  • Console.Out.Flush(); — для языка C#
  • flush(output); — для языка Pascal