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

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

Нервная система монстра может быть представлена как дерево$$$^{\dagger}$$$ из $$$n$$$ вершин (на самом деле, всё не должно постоянно напоминать деревья$$$\ldots$$$), пронумерованных от $$$0$$$ до $$$n-1$$$, с вершиной $$$0$$$ в качестве корня.

Цель Гретель — узнать точную структуру нервной системы монстра. Более конкретно, она хочет узнать значения $$$p_1, p_2, \ldots, p_{n-1}$$$ дерева, где $$$p_i$$$ ($$$0 \le p_i < i$$$) является прямым предком вершины $$$i$$$ ($$$1 \le i \le n - 1$$$).

Она не знает точно, как расположены вершины, но знает несколько приятных фактов:

• Если мы удалим корневую вершину $$$0$$$ и все смежные ребра, то это дерево превратится в лес, состоящий только из путей$$$^{\ddagger}$$$. Каждая вершина, которая изначально была смежной с вершиной $$$0$$$, будет концом какого-то пути.
• Вершины нумеруются таким образом, что если $$$1 \le x \le y \le n - 1$$$, то $$$p_x \le p_y$$$.
• Вершина $$$1$$$ гарантированно имеет ровно две смежные вершины (включая вершину $$$0$$$).

Дерево на этой картинке не удовлетворяет условию, потому что если мы удалим вершину $$$0$$$, то вершина $$$2$$$ (которая изначально была смежной с вершиной $$$0$$$) не будет концом пути $$$4-2-5$$$.	Дерево на этой картинке не удовлетворяет условию, потому что должно выполняться $$$p_3 \le p_4$$$.	Дерево на этой картинке не удовлетворяет условию, потому что вершина $$$1$$$ имеет только одну смежную вершину.

Гретель может делать запросы к защитной камере:

• «? a b» ($$$1 \le a, b < n$$$, $$$a \ne b$$$) — камера проверит, содержит ли простой путь между вершинами $$$a$$$ и $$$b$$$ вершину $$$0$$$.

Однако, чтобы избежать неожиданных последствий от чрезмерной стимуляции существа, Гретель хочет сделать не более $$$2n - 6$$$ запросов. Хотя Гретель одарена, она не может сделать всё сразу, так что можете ли вы протянуть ей руку помощи?

$$$^{\dagger}$$$Дерево — это связный граф, в котором каждая пара различных вершин имеет ровно один простой путь, соединяющий их.

$$$^{\ddagger}$$$Путь — это дерево, вершины которого могут быть записаны в порядке $$$v_1, v_2, \ldots, v_k$$$ так, что рёбра имеют вид $$$(v_i, v_{i+1})$$$ ($$$1 \le i < k$$$).

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

Затем вы можете делать запросы следующего вида:

• «? a b» (без кавычек) ($$$1 \le a, b < n$$$, $$$a \ne b$$$).

После запроса прочитайте целое число $$$r$$$ — ответ на ваш запрос. Вам разрешено использовать не более $$$2n - 6$$$ запросов этого типа.

• Если простой путь между вершинами $$$a$$$ и $$$b$$$ не содержит вершину $$$0$$$, вы получите $$$r = 0$$$.
• Если простой путь между вершинами $$$a$$$ и $$$b$$$ содержит вершину $$$0$$$, вы получите $$$r = 1$$$.
• В случае, если вы сделаете более $$$2n-6$$$ запросов или сделаете некорректный запрос, вы получите $$$r = -1$$$. После получения такого ответа ваша программа должна немедленно завершиться, чтобы получить вердикт «Неправильный ответ». В противном случае вы можете получить произвольный вердикт, потому что ваше решение продолжит чтение из закрытого потока.

Когда вы определите структуру, выведите строку в формате «! $$$p_1 \space p_2 \ldots p_{n-1}$$$» (без кавычек), где $$$p_i$$$ ($$$0 \le p_i < i$$$) обозначает индекс прямого предка вершины $$$i$$$. Этот запрос не учитывается в лимите $$$2n - 6$$$ запросов.

После решения одного набора входных данных программа должна сразу же переходить к следующему. После решения всех наборов входных данных программа должна быть немедленно завершена.

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

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

Интерактор неадаптивный. Дерево не меняется в процессе взаимодействия.

Взломы

Для взлома используйте следующий формат:

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$4 \le n \le 10^4$$$) — количество вершин в нервной системе Генокракена.

Вторая строка каждого набора входных данных содержит $$$n-1$$$ целых чисел $$$p_1, p_2, \ldots, p_{n-1}$$$ ($$$0 \le p_1 \le p_2 \le \ldots \le p_{n-1} \le n - 2$$$, $$$0 \le p_i < i$$$) — прямые предки вершин $$$1$$$, $$$2$$$, ..., $$$n-1$$$ в системе соответственно.

В каждом наборе входных данных значения $$$p_1, p_2, \ldots, p_{n-1}$$$ должны обеспечивать следующее в дереве:

• Если мы удалим корневую вершину $$$0$$$ и все смежные ребра, то это дерево превратится в лес, состоящий только из путей. Каждая вершина, которая изначально была смежной с вершиной $$$0$$$, будет концом какого-то пути.
• Вершина $$$1$$$ имеет ровно две смежные вершины (включая вершину $$$0$$$).

Сумма $$$n$$$ по всем наборам входных данных не должна превышать $$$10^4$$$.