E. Six-Seven Bags
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

Ale and Sofia want to win every aura battle in the city, so they are preparing a street-magic trick with bags of coins.

There are $$$n$$$ bags on a table. The $$$i$$$-th bag contains $$$a_i$$$ coins. In every bag, all coins are of the same type: either $$$6$$$-coins, which weigh $$$6$$$ grams each, or $$$7$$$-coins, which weigh $$$7$$$ grams each. Exactly one bag contains $$$6$$$-coins, and the other $$$n - 1$$$ bags contain $$$7$$$-coins. Ale and Sofia know the array $$$a$$$, but not which bag contains the $$$6$$$-coins.

In one query, they may select any number of coins from each bag (possibly zero) and learn their total weight. All selected coins are returned to their bags after each query.

Let $$$f(a)$$$ be the minimum number of queries needed to guarantee finding the $$$6$$$-coin bag, regardless of which bag it is. Help Ale and Sofia find this bag using at most $$$f(a)$$$ queries.

The interactor is adaptive. The index of the $$$6$$$-coin bag may change during the interaction, as long as all previous answers remain consistent.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of bags.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the number of coins in each bag.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Interaction

For each test case, first read $$$n$$$ and the array $$$a$$$. Then you may make queries.

To make a query, output a line in the following format:

  • ? $$$b_1\; b_2\; \ldots\; b_n$$$ ($$$0 \le b_i \le a_i$$$) — where $$$b_i$$$ is the number of coins selected from the $$$i$$$-th bag.

After each query, read a single integer — the total weight of the selected coins, $$$\sum_{i=1}^{n} b_i \cdot w_i$$$, where $$$w_i = 6$$$ if the $$$i$$$-th bag contains $$$6$$$-coins and $$$w_i = 7$$$ otherwise. This weight may exceed the range of a $$$32$$$-bit integer.

When you have determined the $$$6$$$-coin bag, output a line in the following format:

  • ! $$$i$$$ ($$$1 \le i \le n$$$) — where $$$i$$$ is the index of the bag with $$$6$$$-coins.
This line does not count toward the limit of $$$f(a)$$$ queries. After a correct answer, proceed to the next test case, or terminate your program if it was the last test case. The interactor does not send a confirmation value after a correct answer.

If you exceed the query limit or report an incorrect bag, the interactor will output -1, and you will receive a Wrong Answer verdict. Upon receiving -1 instead of any expected input, your program must terminate immediately. Otherwise, you may receive an arbitrary verdict because your program might try to read from a closed stream. Invalid output may also cause the interactor to terminate immediately.

After printing a query or the answer, output a newline and flush the output. Otherwise, you may receive an Idleness Limit Exceeded verdict. To flush the output, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • sys.stdout.flush() in Python;
  • std::io::stdout().flush() in Rust;
  • see the documentation for other languages.

Hacks

To hack, use the following format.

The first line should contain the number of test cases $$$(1 \le t \le 5000)$$$. The description of the test cases follows.

The first line of each test case should contain an integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of bags — followed by the string manual, followed by an integer $$$k$$$ ($$$1 \le k \le n$$$) — the index of the $$$6$$$-coin bag.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the number of coins in each bag.

The sum of $$$n$$$ over all test cases should not exceed $$$10^5$$$.

Example
Input
2
5
1 1 2 2 2

34

33

4
3 2 4 3

47
Output



? 1 0 1 2 1

? 1 1 2 0 1

! 3


? 3 2 2 0

! 2
Note

The example interaction does not represent an optimal strategy and is only shown to demonstrate the input/output format.

The extra blank lines in the example are for readability only and are not part of the actual input or output.

In the first test case, $$$n = 5$$$ and $$$a = [1, 1, 2, 2, 2]$$$. The third bag contains $$$6$$$-coins. The displayed weights are calculated as follows:

  • ? 1 0 1 2 1: five coins are selected and $$$b_3 = 1$$$, giving $$$7 \cdot (1 + 0 + 2 + 1) + 6 \cdot 1 = 34$$$.
  • ? 1 1 2 0 1: five coins are selected and $$$b_3 = 2$$$, giving $$$7 \cdot (1 + 1 + 0 + 1) + 6 \cdot 2 = 33$$$.
The participant then outputs ! 3 to identify the third bag.

In the second test case, $$$n = 4$$$ and $$$a = [3, 2, 4, 3]$$$. The second bag contains $$$6$$$-coins. The query ? 3 2 2 0 selects seven coins, including two from the second bag, so the response is $$$7 \cdot (3 + 2 + 0) + 6 \cdot 2 = 47$$$.

The participant then outputs ! 2. This answer is correct for the illustrated choice of the hidden bag, but the query does not distinguish the second bag from the third bag.