This is an interactive problem.
There are $$$n$$$ snakes on the number line. The $$$i$$$-th snake is located at the position $$$a_i$$$ and has a speed $$$s_i$$$. You know the position of each snake, and that the speed of each snake is an integer from $$$0$$$ to $$$2$$$ inclusive, but you do not know the exact speed of each snake. It is guaranteed that no two snakes are at the same position.
To figure out the snakes' speed, you may give up to $$$3$$$ instructions. Each instruction should be given in the form of a binary string of length $$$m$$$ containing letters L and R ($$$1 \leq m \leq 4n$$$). After receiving this instruction, the snakes will move for $$$m$$$ seconds. On the $$$i$$$-th second, if $$$s_i=$$$L, then all snakes move left for that second. Otherwise, all snakes move right for that second. If two snakes are at the same location at any given point (including if the time is not an integer number of seconds), the faster snake is removed from the board. After all $$$m$$$ seconds have passed, you are given the number of remaining snakes, as well as the location of all remaining snakes. Note that each instruction is independent of each other – that means that all snakes are revived and moved to their original positions.
Your task is to find the speed of all snakes. However, it may be the case that it is impossible to find the speed of at least one snake. If this is the case, you must report -1 instead. You should only output -1 if it is impossible to figure out the speed of at least one snake, no matter which instructions are given. If you report -1 when there are a series of at most $$$3$$$ instructions that will uniquely determine the speed of each snake, you will get the Wrong Answer verdict. Similarly, you will receive the Wrong Answer verdict if you did not report -1 when the configuration is impossible to determine, even if you correctly guessed the speeds.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.
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 \leq a_1 \lt a_2 \lt \ldots \lt a_n \leq 4n$$$) – the initial position of all snakes.
It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$.
After reading in the position of all snakes, interaction begins. To give an instruction, output a line in the following format:
You should guarantee that $$$s$$$ contains only letters L and R, and has length between $$$1$$$ and $$$4n$$$ inclusive.
The jury will return a line in the following format:
Here, $$$k$$$ is the number of snakes that remain after the full instruction, and $$$b_1,b_2,\ldots,b_k$$$ are their final positions.
When you are ready to output the answer, output a line in the following format:
Printing the answer does not count as giving an instruction.
After this, proceed to the next case or terminate the program if this is the last test case.
The interactor is not adaptive. This means that the speed of all snakes is fixed in advance and does not change in the interaction process. It is further guaranteed that there exists a solution – that is, the resulting positions of all snakes after movements are consistent with their speeds.
After printing each query do not forget to output the end of line and flush$$$^{\text{∗}}$$$ the output. Otherwise, you will get Idleness limit exceeded verdict.
If, at any interaction step, you read $$$-1$$$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.
Hacks
To make a hack, use the following format:
The first line should contain an integer $$$t$$$ — the number of test cases ($$$1 \leq t \leq 10^3$$$).
The first line of each test case should contain an integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$).
The second line of each test case should contain $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_1 \lt a_2 \lt \ldots \lt a_n \leq 4n$$$) – indicating the position of each snake.
The third line of each test case should contain $$$n$$$ integers $$$s_1,s_2,\ldots,s_n$$$ ($$$0 \leq s_i \leq 2$$$) – indicating the speed of each snake.
The sum of $$$n$$$ across all test cases should not exceed $$$10^5$$$.
$$$^{\text{∗}}$$$To flush, use:
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
? 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
In the first test case, the speed of the snakes is $$$0$$$ and $$$1$$$. The program begins by giving the instruction L. The right snake moves from $$$2$$$ to $$$1$$$ while the left snake does not move. However, since now both snakes occupy the position $$$1$$$, the one with the higher speed (the right snake) is removed. Therefore, there is only one snake remaining, and it is at position $$$1$$$. At this point, the program decides to guess the speed of snakes as $$$0$$$ and $$$1$$$, which is correct, so this test case is passed. Note that although the speeds $$$[0,2]$$$ would also result in there being $$$1$$$ snake at position $$$1$$$ at the end, we cannot report $$$-1$$$, as we can show there is a series of instructions that will differentiate $$$[0,2]$$$ and $$$[0,1]$$$.
In the third test case, we conclude that the speed of both the first snake and the third snake is $$$0$$$, and we can show there is no way to differentiate the speed of the middle snake between $$$1$$$ and $$$2$$$. Therefore, reporting -1 is correct in this case.
| Hello 2026 |
|---|
| Finished |
