This is an interactive problem.

On planet KSA, there are $N$ islands. The islands are numbered $1$ to $N$, and island $i$ has $w_i$ amount of resources. No two different islands have the same amount of resources. Between the islands, there are $N-1$ bidirectional underwater passages, and it is guaranteed that any two islands can be reached from one another using only underwater passages. In other words, the structure formed by the islands and underwater passages is a tree.

After realizing that underwater passages on planet KSA are not visible from other planets, Alice, the king of planet KSA, plans to additionally construct $N-1$ bidirectional ground bridges connecting pairs of islands. Using only these bridges, it must also be possible to travel between any two islands. That is, the bridge structure must also form a tree.

Once Alice finishes building the bridges, Bob, the king of planet Automata, begins trying to uncover information. At this time, the island numbers are arbitrarily reassigned, and from then on, every island number Bob observes or uses follows this reassigned numbering system.

Bob must determine $x(i,j)$ for all $1 \le i,j \le N$ by looking only at the ground bridges built by Alice, where

Here, the starting island number $i$, destination island number $j$, and the number of the island with the maximum resource amount are all based on the reassigned numbering system. The path from island number $i$ to island number $j$ includes both island number $i$ and island number $j$.

Before determining all values of $x(i,j)$, Bob may ask the following question at most $100$ times for additional information:

• `?` $i$ $j$ : What is $x(i,j)$?

Since interplanetary communication is very expensive, fewer questions result in a higher score.

Your program is executed twice for each judging data. In the first execution, it must play the role of Alice, and in the second execution, it must play the role of Bob.

The first line contains an integer $S$, indicating the execution step. $S=1$ means to play as Alice, and $S=2$ means to play as Bob.

Alice's Role

Input: The input consists of one or more test cases. The second line contains the number of test cases, $T$. Each test case is given as follows.

The first line contains the number of islands, $N$.

The second line contains $N$ space-separated integers $w_1, w_2, \cdots, w_N$.

Each of the next $N-1$ lines contains two space-separated integers $u$, $v$, the endpoints of an underwater passage.

Output: Output $N-1$ lines, each containing two space-separated integers $u$ and $v$ that are the endpoints of a ground bridge to construct. The order in which the bridges are printed does not matter, and the order of the two endpoints in each bridge also does not matter.

Bob's Role

Interaction: The input consists of one or more test cases. The second line contains the number of test cases, $T$. Each test case is given as follows.

The first line contains the number of islands, $N$.

Each of the next $N-1$ lines contains two space-separated integers $u$, $v$, the endpoints of a ground bridge built by Alice. Note that $u$ and $v$ use the reassigned numbering system, and the order of bridges Bob receives may differ from the order Alice printed them.

For additional information, when the following query is printed, the next line will contain the value of $x(i,j)$. This query can be used at most $100$ times per test case.

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

To submit an answer, print `!` , and then print the answer over the next $N$ lines. On the $i$-th of the $N$ lines, $x(i,1), x(i,2), \cdots, x(i,N)$ must be printed separated by spaces. This query does not count as a question, and the interaction for the corresponding test case ends immediately after printing.

If the interaction ends for a test case that is not the last, it must immediately proceed to the next test case. If the interaction for the final test case ends, the program must terminate immediately.

However, if more than $100$ questions were asked in a single test case, the response to the query will be given as `-1` , indicating that the allowed number of questions was exceeded. In this case, your program must terminate immediately, and the result will be judged as Wrong Answer.

Constraints

• $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$
• If $i \ne j$, then $w_i \neq w_j$

Scoring

For each judging data, let $Q$ be the maximum number of questions asked among all test cases. The score for that judging data is determined as follows.

The score of your submission is the minimum score over all judging data sets. However, unexpected results may happen if you do not print the solution through proper interactions in the limitations of the problem provided.

Examples

Input 1

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



2
10 1
1 2

Output 1

1 4
2 3
3 4



1 2

Input 2

2
2
4
1 3
1 4
2 3

4

1





2
1 2

2

Output 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

Note

In Example 1, since $S = 1$, your program must play the role of Alice.

In Example 2, since $S = 2$, your program must play the role of Bob.

In the first test case, vertices $1, 2, 3, 4$ from the first execution were reassigned to vertices $2, 4, 1, 3$, respectively.

In the second test case, vertices $1, 2$ from the first execution were reassigned to vertices $2, 1$, respectively.

You must flush the output immediately after printing something. To flush you can use:

• C --- `fflush(stdout)`
• C++ --- `std::cout.flush()`
• Python --- `sys.stdout.flush()`
• Java --- `System.out.flush()`
• read the documentation for other languages.

Also, note that the empty lines in the example input and output are for the sake of clarity, and do not occur in the real interaction.