Sum Graph
Contest: Codeforces Round 865 (Div. 1)
Difficulty rating: 2000
Tags: brute force, constructive algorithms, graphs, implementation, interactive, shortest paths, trees

This is an interactive problem.

There is a hidden permutation $$$p_1, p_2, \dots, p_n$$$.

Consider an undirected graph with $$$n$$$ nodes only with no edges. You can make two types of queries:

1. Specify an integer $$$x$$$ satisfying $$$2 \le x \le 2n$$$. For all integers $$$i$$$ ($$$1 \le i \le n$$$) such that $$$1 \le x-i \le n$$$, an edge between node $$$i$$$ and node $$$x-i$$$ will be added.
2. Query the number of edges in the shortest path between node $$$p_i$$$ and node $$$p_j$$$. As the answer to this question you will get the number of edges in the shortest path if such a path exists, or $$$-1$$$ if there is no such path.

Note that you can make both types of queries in any order.

Within $$$2n$$$ queries (including type $$$1$$$ and type $$$2$$$), guess two possible permutations, at least one of which is $$$p_1, p_2, \dots, p_n$$$. You get accepted if at least one of the permutations is correct. You are allowed to guess the same permutation twice.

A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 10^3$$$) — the length of the permutation.

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

Interaction format:
The interaction for each test case begins by reading the integer $$$n$$$.

Then, make at most $$$2n$$$ queries:

- If you want to make a type $$$1$$$ query, output "+ x". $$$x$$$ must be an integer between $$$2$$$ and $$$2n$$$ inclusive. After doing that read $$$1$$$ or $$$-2$$$. If you read $$$1$$$ your query was valid, otherwise it was invalid or you exceed the limit of queries, and your program must terminate immediately to receive a Wrong Answer verdict.
- If you want to make a type $$$2$$$ query, output "? i j". $$$i$$$ and $$$j$$$ must be integers between $$$1$$$ and $$$n$$$ inclusive. After that, read in a single integer $$$r$$$ ($$$-1 \le r \le n$$$) — the answer to your query. If you receive the integer $$$−2$$$ instead of an answer, it means your program has made an invalid query, or has exceeded the limit of queries. Your program must terminate immediately to receive a Wrong Answer verdict.

At any point of the interaction, if you want to guess two permutations, output "! $$$p_{1,1}$$$ $$$p_{1,2}$$$ $$$\dots$$$ $$$p_{1,n}$$$ $$$p_{2,1}$$$ $$$p_{2,2}$$$ $$$\dots$$$ $$$p_{2,n}$$$". Note that you should output the two permutations on the same line, and no exclamation mark is needed to separate the two permutations. After doing that read $$$1$$$ or $$$-2$$$. If you read $$$1$$$ your answer was correct, otherwise it was incorrect and your program must terminate immediately to receive a Wrong Answer verdict. After that, move on to the next test case, or terminate the program if there are none. Note that reporting the answer does not count as a query.

Note that even if you output a correct permutation, the second permutation should be a permutation and not an arbitrary array.

At any point, if you continue interaction after reading in the integer $$$-2$$$, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing a query or the answer do not forget to output the 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 the documentation for other languages.

Interactor is non-adaptive. This means that all permutations are fixed before the interaction starts.

Hacks

To make a hack, use the following format.

The first line should contain a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

The first line of each test case should contain a single integer $$$n$$$ ($$$2 \le n \le 10^3$$$) — the length of the permutation.

The second line of each test case should contain $$$n$$$ distinct integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) — the hidden permutation.

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

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test case, $$$n=6$$$ and the hidden permutation $$$p = [1,4,2,5,3,6]$$$.

Firstly, make a type $$$1$$$ query on $$$x=12, 2, 3$$$ respectively. This adds four edges to the graph in total:

- An edge that connects node $$$6$$$ and node $$$6$$$.
- An edge that connects node $$$1$$$ and node $$$1$$$.
- An edge that connects node $$$1$$$ and node $$$2$$$.
- An edge that connects node $$$2$$$ and node $$$1$$$.

Since all of these queries are valid, the interactor returns $$$1$$$ after each of them.

Then, query the number of edges in the shortest path between node $$$p_1 = 1$$$ and $$$p_3 = 2$$$, which is equal to $$$1$$$.

Then, make a type $$$1$$$ query on $$$x=5$$$. This adds four edges to the graph in total:

- An edge that connects node $$$1$$$ and node $$$4$$$.
- An edge that connects node $$$2$$$ and node $$$3$$$.
- An edge that connects node $$$3$$$ and node $$$2$$$.
- An edge that connects node $$$4$$$ and node $$$1$$$.

Since this query is valid, the interactor returns $$$1$$$.

Then, query the number of edges in the shortest path between node $$$p_1 = 1$$$ and $$$p_5 = 3$$$, which is equal to $$$2$$$.

Then, query the number of edges in the shortest path between node $$$p_4 = 5$$$ and $$$p_5 = 3$$$. Such a path doesn't exist, therefore the interactor returns $$$-1$$$.

Afterwards, due to some magic, two possible permutations that can be $$$p$$$ are determined: the first permutation is $$$[1,4,2,5,3,6]$$$ and the second permutation is $$$[1,2,3,4,5,6]$$$. Since the first permutation is equal to the hidden permutation, this test case is solved correctly. In total, $$$7$$$ queries are used, which is within the limit of $$$2 \cdot 6 = 12$$$ queries.

Since the answer is correct, the interactor returns $$$1$$$.

In the second test case, $$$n=2$$$ and the hidden permutation is $$$p = [2,1]$$$.

Since there are only $$$2! = 2$$$ possible permutations, no queries are needed. It is sufficient to just output the two permutations, $$$[1,2]$$$ and $$$[2,1]$$$. In total, $$$0$$$ queries are used, which is within the limit of $$$2 \cdot 2 = 4$$$ queries.

Since the answer is correct, the interactor returns $$$1$$$.

Example input:
2
6

1

1

1

1

1

2

-1

1
2

1

Example output:
+ 12

+ 2

+ 3

? 1 3

+ 5

? 1 5

? 4 5

! 1 4 2 5 3 6 1 2 3 4 5 6


! 1 2 2 1

Editorial:
Hint 1: Consider using a type 1 operation on $$$x=n+1$$$ and $$$x=n+2$$$. What do you notice?
Hint 2: The resulting graph, after performing type 1 operations according to hint 1, will be a chain (e.g. when $$$n=6$$$, it should look like $$$1 - 6 - 2 - 5 - 3 - 4$$$). Now, try to figure out a position $$$k$$$ such that node $$$p_k$$$ is one of the endpoints of the chain. Once you figure that out, how can you make use of this to solve the full problem?
Editorial: There are many ways to solve this problem. My original solution is rather difficult to implement correctly, and a bit complicated. During round testing, tester [user:rsj] found an alternative solution, which is, in my opinion, one that's a lot easier to understand and implement.
Firstly, use a type 1 operation on $$$x=n+1$$$ and $$$x=n+2$$$ (or you can do $$$x=n$$$ and $$$x=n+1$$$). Then, the graph should look like a chain (e.g. when $$$n=6$$$, it should look like $$$1 - 6 - 2 - 5 - 3 - 4$$$). Note that there are actually two edges between each pair of directly connected nodes, but it is irrelevant to the task.
Next, use a type 2 query on all pairs of $$$(1,i)$$$ where $$$2 \le i \le n$$$. Take the maximum of the query results. Let $$$k$$$ be one of the values such that the query result of $$$(1,k)$$$ is maximum among all $$$(1,i)$$$. It is easy to see that, node $$$p_k$$$ is one of the endpoints of the chain.
Afterwards, use a type 2 query on all pairs of $$$(k,i)$$$ where $$$1 \le i \le n$$$ and $$$i \ne k$$$. Since node $$$p_k$$$ is an endpoint of the chain, all the query results are distinct and you can recover the exact node that each query result corresponds to.
A problem arises that it is unclear about which endpoint node $$$p_k$$$ actually is. But this issue can be solved easily: since the problem allows outputting two permutations that can be $$$p$$$, just try both endpoints and output the corresponding permutations.
In total, $$$2$$$ type 1 operations and $$$2n-2$$$ type 2 operations are used, which sums up to $$$2n$$$ operations. As stated in the sample description, you don't even need any operations when $$$n=2$$$. It is also easy to see that the actual number of operations required is $$$2n-1$$$ since there is a pair of duplicate type 2 operations, but we allow duplicating the operation anyway.