B. Sum Graphtime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis 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:  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.  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).InputEach 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.InteractionThe 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.HacksTo 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.ExampleInput
2
6

1

1

1

1

1

2

-1

1
2

1
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

NoteIn 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.
2
6

1

1

1

1

1

2

-1

1
2

1

  + 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  
['brute force', 'constructive algorithms', 'graphs', 'implementation', 'interactive', 'shortest paths', 'trees', '*2000']