Q. Rigo's Bathtub
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Rigo wants to take a bath, and for that, he needs to fill his bathtub. Rigo has $$$n$$$ buckets of water, each containing $$$p_i$$$ liters, where $$$p$$$ is a permutation of size $$$n$$$. Additionally, his bathtub can hold $$$2n-1$$$ liters if the water is cold and $$$2n+1$$$ liters if it is hot. Although Rigo is a very good mathematician, he is disorganized and has forgotten to label each bucket with its volume, so he asks for your help to assign each bucket its corresponding label in liters.

To do this, you can ask two types of questions:

  1. You provide a set of buckets $$$a_0, a_1, \ldots, a_m$$$ $$$(1 \le a_i \le n$$$, and such that there are no $$$i \neq j$$$ with $$$a_i = a_j$$$) and the temperature, cold or hot. In response, Rigo will tell you if you can fit the $$$m$$$ buckets of water at that temperature in the bathtub.
  2. You can ask Javi for help. If you give Javi a number $$$r$$$ $$$(1 \le r \le n)$$$, Javi will tell you which $$$i$$$ satisfies $$$p_i = r$$$, but since he is busy playing CS:GO, it will cost you dearly to ask him.

Write a program that returns the permutation $$$p$$$ without running out of coins, making at most $$$2$$$ questions of type $$$2$$$ and $$$100000$$$ questions of type $$$1$$$.

Input

The first line of the input contains a single integer $$$T$$$, the number of cases to solve. $$$(1 \le T \le 10)$$$.

Each case starts with a single integer $$$n$$$, the number of buckets, followed by the interaction. $$$(1 \le n \le 6000)$$$.

It is guaranteed that the sum of $$$n$$$ over all tests does not exceed $$$6000$$$.

Interaction

To make a type $$$1$$$ question, the program must have the following format.

  • "$$$1$$$ $$$m$$$ $$$c$$$ $$$a_0$$$ $$$a_1$$$ $$$\ldots$$$ $$$a_m$$$" (without quotes). Where $$$m$$$ is the number of buckets you want to include, $$$a_i$$$ are the indices of the buckets you include, and $$$c$$$ is a character that must be 'F' or 'C', where 'F' denotes that the temperature of the water is cold and 'C' that it is hot. There cannot be repeated elements in $$$a$$$.
To a type $$$1$$$ question, the judge will respond with an integer $$$x$$$. $$$x$$$ is $$$1$$$ if the water from all the buckets at that temperature fits in Rigo's bathtub, and $$$0$$$ otherwise.

To make a type $$$2$$$ question, the format must be as follows:

  • "$$$2$$$ $$$r$$$" (without quotes). Where $$$r$$$ is the amount of water for which you want to know which bucket has exactly $$$r$$$ liters.
To a type $$$2$$$ question, the judge will respond with an integer $$$i$$$, indicating that $$$p_i = r$$$.

Finally, to provide the answer, the program must print a single line in the following format:

  • "! $$$p_0$$$ $$$p_1$$$ $$$\ldots$$$ $$$p_n$$$" (without quotes).
After that, the program should continue to the next case or terminate if it was already at the last case.

If your program asks more than $$$2$$$ questions of type $$$2$$$ or $$$10^5$$$ questions of type $$$1$$$ for a test case, it must terminate immediately to receive the verdict Wrong Answer. Otherwise, you could receive an arbitrary verdict because your solution will attempt to continue reading from a closed stream.

Additionally, the sum of $$$m$$$ over all questions of type $$$1$$$ over all tests must not exceed $$$10^7$$$.

After printing a question or the answer, do not forget to write the end-of-line character and flush the output buffer. Otherwise, you might get the verdict Time limit exceeded. To do this, use:

  • fflush(stdout) or cout.flush() in C++.
  • System.out.flush() in Java.
  • stdout.flush() in Python.
  • Check the documentation for other languages.
Example
Input
1
5
1
0
1
3
Output
2 3
1 3 F 1 4 2
1 3 C 1 4 2
2 4
! 3 2 4 5 1
Note

Note that, with the questions asked, you are not guaranteed that the answer is correct. This sample is just for illustrative effect.