CF2134E Power Boxes

This is an interactive problem. You are given $n$ boxes, indexed from $1$ to $n$. The boxes look identical, but each one has a hidden power value $a_i$, which is either $1$ or $2$. You want to determine the power value of each box. To do so, you conduct the following experiment. Initially, the $i$-th box is placed at coordinate $i$ on a number line ($1 \le i \le n$). You are allowed to perform the following two types of queries: - "swap $x$" ($1 \le x \le n - 1$): Swap the boxes currently located at coordinates $x$ and $x + 1$. Note that this change is permanent and affects all subsequent queries. - "throw $x$" ($1 \le x \le n$): Throw a ball at the box located at coordinate $x$. The ball travels $p$ units forward to coordinate $x + p$ if the power value of the box is $p$. If there is a box at the new coordinate, the ball jumps again using the power of that box. This continues until the ball lands on a coordinate without a box. As a response, you are given the total number of jumps the ball made before stopping. Your task is to determine the power value of each box using no more than $\left\lceil \dfrac{3n}{2} \right\rceil$ queries in total, counting both swap and throw queries.

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows. The first and the only line of each test case contains a single integer $n$ ($2 \le n \le 1000$) — the number of boxes. It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.

N/A

Below is the interaction process in the example: SolutionJuryExplanation2There are $2$ test cases.4There are $4$ boxes in the first test case. The hidden power values are $a = \[2,1,2,1\]$.throw 22Throw a ball at the box located at coordinate $2$. The ball travels through coordinates $2 \to 3 \to 5$ and stops at coordinate $5$, so the response is $2$.swap 3Swap the boxes located at coordinate $3$ and $4$. Now box $3$ is located at coordinate $4$ and box $4$ is located at coordinate $3$.throw 23Throw a ball at the box located at coordinate $2$. The ball travels through coordinates $2 \to 3 \to 4 \to 6$ and stops at coordinate $6$, so the response is $3$. Note that the response is different because of the swap.throw 13Throw a ball at the box located at coordinate $1$. The ball travels through coordinates $1 \to 3 \to 4 \to 6$ and stops at coordinate $6$, so the response is $3$.! 2 1 2 1The solution concludes that the power values are $\[2,1,2,1\]$.2There are $2$ boxes in the second test case. The hidden power values are $a = \[1, 2\]$.throw 12Throw a ball at the box located at coordinate $1$. The ball travels through coordinates $1 \to 2 \to 4$ and stops at coordinate $4$, so the response is $2$.swap 1Swap the boxes located at coordinate $1$ and $2$. Now box $1$ is located at coordinate $2$ and box $2$ is located at coordinate $1$.throw 11Throw a ball at the box located at coordinate $1$. The ball travels through coordinates $1 \to 3$ and stops at coordinate $3$, so the response is $1$.! 1 2The solution concludes that the power values are $\[1,2\]$.Empty lines in the example input and output are given only for better readability; you don't need to output them in your solution. Note that in the first test case, the given queries are in fact insufficient to uniquely determine the power values; they are given only to illustrate the input/output format.