Это интерактивная задача.
Жюри загадало перестановку \(p\) длины \(n\) и предлагает Вам её угадать. Для этого жюри создало перестановку \(q\) длины \(n\). Изначально \(q\) является тождественной (\(q_i = i\) для всех \(i\)).
За один запрос Вы можете узнать \(q_i\) для любого \(i\). После каждого Вашего запроса жюри будет изменять \(q\) следующим образом:
- Сначала жюри создаст перестановку \(q'\) длины \(n\) такую что \(q'_i = q_{p_i}\) для всех \(i\).
- После этого жюри заменит \(q\) на \(q'\).
Вы можете сделать не более \(2n\) запросов, чтобы угадать перестановку \(p\).
Протокол взаимодействия
Взаимодействие Вашей программы с программой жюри в каждом тестовом случае начинается со считывания числа \(n\) (\(1 \leq n \leq 10^4\)) — длины перестановок \(p\) и \(q\).
Чтобы узнать значение \(q_i\), выведите запрос в формате \(?\) \(i\) (\(1 \leq i \leq n\)). После этого, программа жюри выведет значение \(q_i\).
Вы можете сделать не более \(2n\) запросов. В ответ на некорректный запрос программа жюри выведет \(0\), и после этого Вы должны сразу завершить программу, чтобы получить вердикт Неправильный ответ.
Когда Вы будете готовы сообщить \(p\), выведите \(p\) в формате \(!\) \(p_1\) \(p_2\) \(\ldots\) \(p_n\). После этого следует приступать к обработке следующего тестового случая или завершить программу, если это был последний тестовый случай. Вывод перестановки не считается как один из \(2n\) запросов.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Гарантируется, что сумма \(n\) по всем тестовым случаям не превосходит \(10^4\). Интерактор в этой задаче не является адаптивным.
Взломы:
Чтобы сделать взлом, используйте следующий формат:
В первой строке находится одно целое число \(t\) — количество тестовых случаев.
Описание каждого тестового случая должно состоять из двух строк. В первой строке находится число \(n\) — длина перестановок \(p\) и \(q\). Во второй строке находятся \(n\) чисел \(p_1, p_2, \ldots, p_n\) — перестановка, которую должно загадать жюри в данном тестовом случае.
Примечание
В первом тестовом случае жюри загадало перестановку \(p = [4, 2, 1, 3]\).
Перед первым Вашим запросом \(q = [1, 2, 3, 4]\), ответ на запрос будет равен \(q_3 = 3\).
Перед вторым Вашим запросом \(q = [4, 2, 1, 3]\), ответ на запрос будет равен \(q_2 = 2\).
Перед третьим Вашим запросом \(q = [3, 2, 4, 1]\), ответ на запрос будет равен \(q_4 = 1\).
Во втором тестовом случае жюри загадало перестановку \(p = [1, 3, 4, 2]\).
Пустые строки в примере даны только для улучшения читаемости. В тестирующей системе программа жюри не будет выводить пустые строки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4
3
2
1
4
2
4
4
|
? 3
? 2
? 4
! 4 2 1 3
? 2
? 3
? 2
! 1 3 4 2
|