Наступило Рождество! Пока большинство людей участвуют в обмене подарками «Тайный Санта», на вашем рабочем месте зреет более зловещий план: раскрыть секреты Санты.

У Санты есть список «послушных или непослушных» для каждого человека на Земле. Поскольку его содержимое очень конфиденциально, список написан на северо-польском — загадочном языке с $N$ буквами. Для дополнительной безопасности Санта зашифровал этот список с помощью шифра подстановки: перестановки $H$ чисел $1, 2, \dots, N$, которая отображает каждую северо-польскую букву $i$ в уникальную букву $H(i)$. В таком шифре никакие две буквы не отображаются в одну и ту же целевую букву — формально, если $i \neq j$, то $H(i) \neq H(j)$, — иначе Санта не смог бы расшифровать свой список! (Санта может отображать некоторые буквы сами в себя, $H(i) = i$, просто чтобы быть хитрее.)

К счастью для вас, сервер Санты был плохо защищен и оказался доступен через публичный Интернет. Вы и ваши коллеги надеетесь взломать сервер Санты, расшифровать его список и подтвердить, что вы все в списке непослушных! (Хакеры всегда непослушные.)

Сервер был создан так, чтобы Санта мог быстро проверять свой список на ходу. После того как пользователь подключается к серверу, он предлагает ввести список из $N$ целых чисел $H(1), H(2), \dots, H(N)$, кодирующих перестановку $H$, проверяет правильность этого списка, а затем расшифровывает секретный список Санты. В ходе многомесячных исследований вы обнаружили уязвимость, связанную с временем отклика. Допустим, вы вводите перестановку $Q$. Если $H = Q$, сервер мгновенно предоставляет доступ. В противном случае рассмотрим граф на $N$ вершинах и добавим ребро из каждой вершины $i$ в вершину $H(Q(i))$. Вы обнаружили, что сложный алгоритм аутентификации сервера будет отвечать вам сообщением об ошибке «Access Denied» ровно столько секунд, сколько связных компонент в полученном графе.

Например, предположим, что $N = 4$, а шифрующая перестановка $H$ имеет вид:

Если вы попытаетесь войти на сервер с вводом 4 3 2 1, то, поскольку эта перестановка не совпадает с $H$ и поскольку описанный выше граф имеет две связные компоненты (одна содержит цикл ребер $1 \to 4 \to 2 \to 1$, а другая — только петлю $3 \to 3$), сервер ответит сообщением об ошибке «Access Denied» с задержкой в 2 секунды.

Заметьте, что если вы пытаетесь войти на сервер несколько раз с разными входными данными $Q$, он каждый раз проверяет $Q$ относительно одного и того же сохраненного $H$. Он никак не меняет $H$ в ответ на ваши запросы.

Санта заметит, если его сервер будет забросан неавторизованными запросами. Вы подсчитали, что можете сделать не более 1 510 попыток входа, прежде чем вызовете слишком много подозрений. Можете ли вы найти эффективную стратегию для определения шифрующей перестановки?

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

Это интерактивная задача. Взаимодействие начинается с чтения целого числа $N$ ($1 \le N \le 220$) из стандартного потока ввода — количества букв в северо-польском языке. Судья не является адаптивным: скрытая перестановка $H$ выбирается в этот момент и не меняется на протяжении всего взаимодействия.

Чтобы попытаться войти на сервер, выведите строку с $N$ целыми числами $Q(1), \dots, Q(N)$, разделенными пробелами, где $Q$ — перестановка $\{1, 2, \dots, N\}$. Затем прочитайте одно целое число из стандартного потока ввода — количество секунд, которое требуется серверу для ответа на ваш запрос.

Если эта задержка равна 0, вы успешно нашли шифрующую перестановку $H$, и ваша программа должна завершиться. Если нет, эта задержка равна количеству связных компонент в графе, построенном согласно описанной выше процедуре.

Вы можете попытаться войти в систему не более 1 510 раз. Если у вас закончатся попытки, ваша программа должна корректно завершиться (хотя она будет оценена как неверная за неспособность расшифровать список Санты).

Примечание

Не забудьте очистить (сбросить) выходной поток после каждой выведенной строки и корректно завершить работу после окончания взаимодействия. Пожалуйста, убедитесь, что вы точно следуете протоколу взаимодействия относительно того, какую информацию выводить на какой строке: например, если протокол требует вывести список целых чисел через пробел на одной строке, судья не примет каждое число на отдельной строке.

Если судья получит неверные или неожиданные данные, он выведет $-1$ и немедленно завершит работу. Ваша программа должна обнаружить это и корректно завершиться, чтобы получить вердикт «Wrong Answer». Если ваша программа блокируется в ожидании дальнейшего взаимодействия от судьи или пытается интерпретировать $-1$ как количество компонент, вы можете получить другой вердикт (например, «Time Limit Exceeded» или «Runtime Error») вместо «Wrong Answer».

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

Примеры

Пример 1

3

1 2 3

1

2 1 3

2

3 1 2

0