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

На планете KSA есть $N$ островов. Острова пронумерованы от $1$ до $N$, и на острове $i$ находится $w_i$ ресурсов. Никакие два острова не имеют одинакового количества ресурсов. Между островами проложено $N-1$ двусторонних подводных переходов, и гарантируется, что любые два острова можно соединить друг с другом, используя только эти переходы. Другими словами, структура, образованная островами и подводными переходами, является деревом.

Осознав, что подводные переходы на планете KSA не видны с других планет, Алиса, королева планеты KSA, планирует дополнительно построить $N-1$ двусторонний наземный мост, соединяющий пары островов. Используя только эти мосты, также должно быть возможно добраться от любого острова до любого другого. То есть структура мостов также должна образовывать дерево.

Как только Алиса заканчивает строительство мостов, Боб, король планеты Automata, начинает попытки раскрыть информацию. В этот момент номера островов произвольно переназначаются, и с этого момента каждый номер острова, который Боб видит или использует, следует этой новой системе нумерации.

Боб должен определить $x(i,j)$ для всех $1 \le i,j \le N$, глядя только на наземные мосты, построенные Алисой, где

Здесь начальный номер острова $i$, конечный номер острова $j$ и номер острова с максимальным количеством ресурсов основаны на переназначенной системе нумерации. Путь от острова $i$ до острова $j$ включает в себя как остров $i$, так и остров $j$.

Перед определением всех значений $x(i,j)$ Боб может задать следующий вопрос не более $100$ раз для получения дополнительной информации:

• `?` $i$ $j$ : Чему равно $x(i,j)$?

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

Ваша программа выполняется дважды для каждого набора данных. В первом выполнении она должна играть роль Алисы, а во втором — роль Боба.

Первая строка содержит целое число $S$, указывающее этап выполнения. $S=1$ означает игру за Алису, а $S=2$ означает игру за Боба.

Роль Алисы

Входные данные: Входные данные состоят из одного или нескольких тестов. Вторая строка содержит количество тестов $T$. Каждый тест задается следующим образом.

Первая строка содержит количество островов $N$.

Вторая строка содержит $N$ целых чисел $w_1, w_2, \cdots, w_N$, разделенных пробелами.

Каждая из следующих $N-1$ строк содержит два целых числа $u$ и $v$, разделенных пробелами — концы подводного перехода.

Выходные данные: Выведите $N-1$ строку, каждая из которых содержит два целых числа $u$ и $v$, разделенных пробелами — концы наземного моста, который нужно построить. Порядок вывода мостов не имеет значения, как и порядок концов в каждом мосте.

Роль Боба

Протокол взаимодействия: Входные данные состоят из одного или нескольких тестов. Вторая строка содержит количество тестов $T$. Каждый тест задается следующим образом.

Первая строка содержит количество островов $N$.

Каждая из следующих $N-1$ строк содержит два целых числа $u$ и $v$, разделенных пробелами — концы наземного моста, построенного Алисой. Заметьте, что $u$ и $v$ используют переназначенную систему нумерации, и порядок мостов, которые получает Боб, может отличаться от порядка, в котором их вывела Алиса.

Для получения дополнительной информации, когда выводится следующий запрос, следующая строка будет содержать значение $x(i,j)$. Этот запрос можно использовать не более $100$ раз для каждого теста.

• `?` $i$ $j$ ($1 \le i, j \le N$)

Чтобы отправить ответ, выведите `!` , а затем выведите ответ в следующих $N$ строках. В $i$-й из $N$ строк должны быть выведены $x(i,1), x(i,2), \cdots, x(i,N)$, разделенные пробелами. Этот запрос не считается вопросом, и взаимодействие для соответствующего теста завершается сразу после вывода.

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

Однако, если в одном тесте было задано более $100$ вопросов, ответом на запрос будет `-1` , что означает превышение допустимого количества вопросов. В этом случае ваша программа должна немедленно завершить работу, и результат будет оценен как Wrong Answer.

Ограничения

• $S \in \{1, 2 \}$
• $1 \le T \le 100$
• $2 \le N \le 100$
• $1 \le u < v \le N$
• $1 \le w_i \le 10^9$
• Если $i \ne j$, то $w_i \neq w_j$

Scoring

Для каждого набора данных пусть $Q$ — максимальное количество вопросов, заданных среди всех тестов. Балл за этот набор данных определяется следующим образом.

Итоговый балл за решение — это минимальный балл среди всех наборов данных. Однако могут возникнуть непредвиденные результаты, если вы не выводите решение через правильное взаимодействие в рамках ограничений задачи.

Примеры

Входные данные 1

1
2
4
3 5 9 4
1 2
2 3
2 4

2
10 1
1 2

Выходные данные 1

1 4
2 3
3 4

1 2

Входные данные 2

2
2
4
1 3
1 4
2 3

4
1

2
1 2

2

Выходные данные 2

? 2 3

? 1 2

!
1 1 1 1
1 2 4 4
1 4 3 4
1 4 4 4

? 1 2

!
1 2
2 2

Примечание

В примере 1, поскольку $S = 1$, ваша программа должна играть роль Алисы.

В примере 2, поскольку $S = 2$, ваша программа должна играть роль Боба.

В первом тесте вершины $1, 2, 3, 4$ из первого выполнения были переназначены в вершины $2, 4, 1, 3$ соответственно.

Во втором тесте вершины $1, 2$ из первого выполнения были переназначены в вершины $2, 1$ соответственно.

Вы должны сбрасывать буфер вывода сразу после вывода чего-либо. Для сброса можно использовать:

• C --- `fflush(stdout)`
• C++ --- `std::cout.flush()`
• Python --- `sys.stdout.flush()`
• Java --- `System.out.flush()`
• ознакомьтесь с документацией для других языков.

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