This is an interactive problem.

There are $n$ snakes on a number line. The $i$-th snake is at position $a_i$ and has a speed $s_i$. You know the position of each snake, and the speed of each snake is an integer from $0$ to $2$, but you do not know the specific speed of each snake. It is guaranteed that no two snakes are at the same position.

To determine the speeds of all snakes, you can issue at most $3$ queries. Each query should be given as a binary string of length $m$ consisting only of L and R ($1 \leq m \leq 4n$). Upon receiving this instruction, all snakes move for $m$ seconds. At the $i$-th second, if the character is L, all snakes move one unit to the left; otherwise, all snakes move one unit to the right. If at any moment (including non-integer time points) two snakes are at the same position, the snake with the higher speed is removed. After $m$ seconds, you will receive the number of remaining snakes $k$, and the positions of all remaining snakes. Note that each query is independent—that is, all snakes are revived and returned to their starting positions before a new operation begins.

Your task is to determine the speed of each snake. However, it is possible that the speed of a certain snake cannot be determined; in such a case, you should output $-1$. You should only output $-1$ if it is impossible to determine the speed of a snake regardless of which set of at most $3$ queries is given. If there exists a set of at most $3$ queries that can uniquely determine all speeds but you output $-1$, you will receive a Wrong Answer verdict. Similarly, if you should have output $-1$ but did not, you will also receive a Wrong Answer verdict, even if you "guessed" the speeds correctly.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$), followed by the descriptions of all test cases.

The first line of each test case contains an integer $n$, the number of snakes ($2 \leq n \leq 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_1 < a_2 < \ldots < a_n \le 4n$), representing the initial positions of all snakes.

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

Output

Interaction Protocol

After reading the positions of all snakes, the interaction begins. Each query must be output as a single line in the following format:

• ? s

You must ensure that $s$ consists only of the letters L and R, and its length is between $1$ and $4n$.

The interactor will return a line in the following format:

• $k\ b_1\ b_2\ \ldots\ b_k$ ($1 \le k \le n, -10^9 \leq b_1 < b_2 < \ldots < b_k \le 10^9$)

where $k$ is the number of remaining snakes after the query, and $b_1, b_2, \ldots, b_k$ are their final positions.

When you are ready to output the answer, output a single line:

• If it is impossible to determine all speeds, output ! -1
• Otherwise, output ! s_1 s_2 \ldots s_n ($0 \leq s_i \leq 2$), where $s_i$ is the speed of the $i$-th snake.

Outputting the answer does not count towards the query limit.

After this, proceed to the next test case or terminate the program.

The interactor is non-adaptive, meaning the speeds of all snakes remain constant throughout the process, and it is guaranteed that the input is valid—that is, all information is consistent with the respective speeds.

After each query, make sure to flush the output buffer; otherwise, you may receive an Idleness limit exceeded verdict.

If you receive $-1$ at any step, it means you have made an invalid query or another error occurred; you should exit immediately, otherwise, the program will continue to read from a closed stream, leading to unpredictable verdicts.

Hack Format

To provide a custom hack, use the following format:

The first line contains an integer $t$, the number of test cases ($1 \leq t \leq 10^3$).

The first line of each test case contains $n$ ($2 \leq n \leq 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_1 < a_2 < \ldots < a_n \le 4n$).

The third line contains $n$ integers $s_1, s_2, \ldots, s_n$ ($0 \leq s_i \leq 2$), representing the speed of each snake.

The sum of $n$ over all test cases does not exceed $10^5$.

To flush the output buffer:

• C++: fflush(stdout) or cout.flush();
• Python: sys.stdout.flush();
• For other languages, please refer to the relevant documentation.

Examples

Input 1

7
2
1 2

1 1

2
1 6

2 1 4

3
2 3 4

2 2 4

3
2 3 4

3 5 6 7

5
1 3 8 14 15

5
1 2 3 4 5

4
5 6 7 8

Output 1

? L

! 0 1


? LRLL

! 0 1


? RRR

! -1


? RRR

! 1 1 1


! 2 1 0 0 1


! 0 2 2 2 0


! 0 1 2 0

Note

In the first test case, the two snakes have speeds $0$ and $1$. The program first issues the query L. The snake on the right moves from $2$ to $1$, while the snake on the left stays put. At this point, both snakes are at $1$, and the snake with the higher speed (the one on the right) is removed. Thus, only one snake remains at position $1$. The program then guesses the speeds of the two snakes are $0$ and $1$, which is correct. Note that although speeds $[0, 2]$ would also result in only one snake remaining at $1$, you cannot simply output $-1$ because it is possible to distinguish between $[0, 2]$ and $[0, 1]$ using another set of queries.

In the third test case, it can be determined that the first and third snakes have a speed of $0$, and it can be proven that it is impossible to distinguish whether the speed of the middle snake is $1$ or $2$, so outputting $-1$ is correct.