Ian and Mary are frogs living on lattice points of the Cartesian coordinate plane, with Ian living on $$$(0,0)$$$ and Mary living on $$$(a,b)$$$.

Ian would like to visit Mary by jumping around the Cartesian coordinate plane. Every second, he jumps from his current position $$$(x_p, y_p)$$$ to another lattice point $$$(x_q, y_q)$$$, such that no lattice point other than $$$(x_p, y_p)$$$ and $$$(x_q, y_q)$$$ lies on the segment between point $$$(x_p, y_p)$$$ and point $$$(x_q, y_q)$$$.

As Ian wants to meet Mary as soon as possible, he wants to jump towards point $$$(a,b)$$$ using at most $$$2$$$ jumps. Unfortunately, Ian is not good at maths. Can you help him?

A lattice point is defined as a point with both the $$$x$$$-coordinate and $$$y$$$-coordinate being integers.

Consider a $$$2 \times n$$$ grid, where $$$n$$$ is an even integer. You may place the integers $$$1, 2, \ldots, 2n$$$ on the grid, using each integer exactly once.

A path is a sequence of cells achieved by starting at $$$(1, 1)$$$, then repeatedly walking either downwards or to the right, and stopping when $$$(2, n)$$$ is reached. The path should not extend beyond the grid.

The cost of a path is the alternating sum of the numbers written on the cells in a path. That is, let the numbers written on the cells be $$$a_1, a_2, \ldots, a_k$$$ (in the order that it is visited), the cost of the path is $$$a_1 - a_2 + a_3 - a_4 + \ldots = \sum_{i=1}^k a_i \cdot (-1)^{i+1}$$$.

Construct a way to place the integers $$$1, 2, \ldots, 2n$$$ on the grid, such that the minimum cost over all paths from $$$(1, 1)$$$ to $$$(2, n)$$$ is maximized. If there are multiple such grids that result in the maximum value, output any of them.

To thank Ian, Mary gifted an array $$$a$$$ of length $$$n$$$ to Ian. To make himself look smart, he wants to make the array in non-decreasing order by doing the following finitely many times: he chooses two adjacent elements $$$a_i$$$ and $$$a_{i+1}$$$ ($$$1\le i\le n-1$$$), and increases both of them by $$$1$$$ or decreases both of them by $$$1$$$. Note that, the elements of the array can become negative.

As a smart person, you notice that, there are some arrays such that Ian cannot make it become non-decreasing order! Therefore, you decide to write a program to determine if it is possible to make the array in non-decreasing order.

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).

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$$$.

You are given an integer $$$n$$$, as well as $$$m$$$ pairs of integers $$$(a_i,b_i)$$$, where $$$1\leq a_i , b_i \leq n$$$, $$$a_i \ne b_i$$$.

You want to construct a sequence satisfying the following requirements:

• All elements in the sequence are integers between $$$1$$$ and $$$n$$$.
• There is exactly one element with value $$$1$$$ in the sequence.
• For each $$$i$$$ ($$$1 \le i \le m$$$), between any two elements (on different positions) in the sequence with value $$$a_i$$$, there is at least one element with value $$$b_i$$$.
• The sequence constructed has the maximum length among all possible sequences satisfying the above properties.

Sometimes, it is possible that such a sequence can be arbitrarily long, in which case you should output "INFINITE". Otherwise, you should output "FINITE" and the sequence itself. If there are multiple possible constructions that yield the maximum length, output any.

Given two positive integers $$$n$$$ and $$$m$$$. Find the sum of all possible values of $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$$$, where $$$a_1,a_2,\ldots,a_m$$$ are non-negative integers such that $$$a_1+a_2+\ldots+a_m=n$$$.

Note that all possible values $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$$$ should be counted in the sum exactly once.

As the answer may be too large, output your answer modulo $$$998244353$$$.

Here, $$$\bigoplus$$$ denotes the bitwise XOR operation.