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

Загадана перестановка $$$p_1, p_2, \dots, p_n$$$.

Рассмотрим неориентированный граф с $$$n$$$ вершинами и без рёбер. Вы можете делать два типа запросов:

1. Укажите целое число $$$x$$$ такое, что $$$2 \le x \le 2n$$$. Тогда для всех целых чисел $$$i$$$ ($$$1 \le i \le n$$$) таких, что $$$1 \le x-i \le n$$$, будет добавлено ребро между вершинами $$$i$$$ и $$$x-i$$$.
2. Запросить число рёбер в кратчайшем пути между вершинами $$$p_i$$$ и $$$p_j$$$. В качестве ответа вы получите количество рёбер на кратчайшем пути, если такой путь существует, или $$$-1$$$, если такого пути нет.

Обратите внимание, что вы можете делать оба типа запросов в любом порядке.

Сделав $$$2n$$$ запросов (включая тип $$$1$$$ и тип $$$2$$$), угадайте две возможные перестановки, хотя бы одна из которых равна $$$p_1, p_2, \dots, p_n$$$. Ваш ответ будет засчитан, если хотя бы одна из перестановок верна. Вы можете вывести одну и ту же перестановку дважды.

Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

Взаимодействие для каждого набора входных данных начинается после считывания $$$n$$$.

Затем, сделайте не более $$$2n$$$ запросов:

• Если вы хотите сделать запрос типа $$$1$$$, выведите «+ x». $$$x$$$ должно быть целым числом от $$$2$$$ до $$$2n$$$ включительно. После этого считайте $$$1$$$ или $$$-2$$$. Если вы считали $$$1$$$, то ваш запрос был корректным, иначе он был некорректным или вы превысили количество запросов, и ваша программа должна немедленно завершиться, чтобы получить вердикт Неправильный ответ.
• Если вы хотите сделать запрос типа $$$2$$$, выведите «? i j». $$$i$$$ и $$$j$$$ должны быть целыми числами от $$$1$$$ до $$$n$$$ включительно. После этого, считайте единственное целое число $$$r$$$ ($$$-1 \le r \le n$$$) — ответ на ваш запрос. Если вы получили число $$$−2$$$ вместо ответа, то ваша программа сделала некорректный запрос или превысила число запросов. Ваша программа должна немедленно завершиться для получения вердикта Неправильный ответ.

В любой момент взаимодействия, если вы хотите угадать две перестановки, выведите «! $$$p_{1,1}$$$ $$$p_{1,2}$$$ $$$\dots$$$ $$$p_{1,n}$$$ $$$p_{2,1}$$$ $$$p_{2,2}$$$ $$$\dots$$$ $$$p_{2,n}$$$». Обратите внимание, что вы должны выводить две перестановки на одной и той же строке и без восклицательного знака между перестановками. После этого считайте $$$1$$$ или $$$-2$$$. Если вы считали $$$1$$$, то ваш ответ был правильным, иначе он был неправильным, и ваша программа должна немедленно завершиться, чтобы получить вердикт Неправильный ответ. После этого, перейдите к следующему набору входных данных, или завершите программу, если такого нет. Обратите внимание, что вывод ответа не считается как запрос.

Обратите внимание, что даже если вы вывели правильную перестановку, вторая перестановка должна быть именно перестановкой, а не произвольным массивом.

В любой момент, если вы продолжите взаимодействие после считывания числа $$$-2$$$, вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока.

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

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

Интерактор является неадаптивным. Это означает, что все перестановки зафиксированы до начала взаимодействия.

Взломы

Чтобы сделать взлом, используйте следующий формат.

Первая строка должна содержать единственное целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных должна содержать единственное целое число $$$n$$$ ($$$2 \le n \le 10^3$$$) — длину перестановки.

Вторая строка каждого набора входных данных должна содержать $$$n$$$ различных целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — загаданную перестановку.

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^3$$$.