Hidden Permutations

This is an interactive problem.

The jury has a permutation $$$p$$$ of length $$$n$$$ and wants you to guess it. For this, the jury created another permutation $$$q$$$ of length $$$n$$$. Initially, $$$q$$$ is an identity permutation ($$$q_i = i$$$ for all $$$i$$$).

You can ask queries to get $$$q_i$$$ for any $$$i$$$ you want. After each query, the jury will change $$$q$$$ in the following way:

• At first, the jury will create a new permutation $$$q'$$$ of length $$$n$$$ such that $$$q'_i = q_{p_i}$$$ for all $$$i$$$.
• Then the jury will replace permutation $$$q$$$ with pemutation $$$q'$$$.

You can make no more than $$$2n$$$ queries in order to quess $$$p$$$.

Interaction in each test case starts after reading the single integer $$$n$$$ ($$$1 \leq n \leq 10^4$$$) — the length of permutations $$$p$$$ and $$$q$$$.

To get the value of $$$q_i$$$, output the query in the format $$$?$$$ $$$i$$$ ($$$1 \leq i \leq n$$$). After that you will receive the value of $$$q_i$$$.

You can make at most $$$2n$$$ queries. After the incorrect query you will receive $$$0$$$ and you should exit immediately to get Wrong answer verdict.

When you will be ready to determine $$$p$$$, output $$$p$$$ in format $$$!$$$ $$$p_1$$$ $$$p_2$$$ $$$\ldots$$$ $$$p_n$$$. After this you should go to the next test case or exit if it was the last test case. Printing the permutation is not counted as one of $$$2n$$$ queries.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^4$$$. The interactor is not adaptive in this problem.

Hacks:

To hack, use the following format:

The first line contains the single integer $$$t$$$ — the number of test cases.

The first line of each test case contains the single integer $$$n$$$ — the length of the permutations $$$p$$$ and $$$q$$$. The second line of each test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ — the hidden permutation for this test case.