P8851 JROI-7 T2nz.

**This is an interactive problem.**

Little X has fallen into a strange dream. In the dream, she is playing a strange kind of chess with Little Q. This is a $2^{2n} \times 2n$ board. Little X plays black and moves first, and Little Q plays white and moves second. In each move, you need to place a piece in **any cell within the first row that is not yet full**. Each cell can contain at most one piece. After the board is filled, there will be $2^{2n}$ rows of pieces in total. Little X’s score is the number of essentially different rows. Little X wants to maximize her score, but Little Q wants to minimize Little X’s score. Your task is to act as Little X or Little Q to maximize or minimize the score. **If you are Little X, while maximizing the score $ans$, you must also maximize the number of essentially different rows among the first $ans$ rows.** ------------ ### Interaction Protocol You should first read a line from standard input containing two integers $T, tp$, representing the number of test cases and the role you play. It is guaranteed that $tp \in \{0, 1\}$. If $tp = 0$, you play as Little Q (second player). If $tp = 1$, you play as Little X (first player). Then for each test case, you should first read a line from standard input containing one positive integer $n$, with the meaning as described above. Then there will be $2^{2n} \times n$ rounds of interaction. In each interaction: - If $tp = 0$, you should first read a line from standard input containing one positive integer $x$, meaning that Little X placed a black piece in column $x$ of the current first not-full row. Then you should output one positive integer $y$ to standard output, meaning that you place a white piece in column $y$ of the current first not-full row. - If $tp = 1$, you should first output one positive integer $x$ to standard output, meaning that you place a black piece in column $x$ of the current first not-full row. Then you should read a line from standard input containing one positive integer $y$, meaning that Little Q placed a white piece in column $y$ of the current first not-full row. All your outputs must **end with a newline and flush the buffer**. You must ensure that the position you play on does not already have a piece. The interactive library will also guarantee that the position it plays on does not already have a piece.

See “Interaction Protocol”.

See “Interaction Protocol”.

**[Sample Explanation]** The input has $n = 1$, so the board size is $4 \times 2$. The two players simulate as shown in the [GIF](https://i.ibb.co/ChCxHQH/e.gif). The final result is shown in the figure below:  It can be observed that the final number of essentially different rows is $2$. It is easy to see that this is the maximum score Little X can achieve. At the same time, among the first $2$ rows, the number of essentially different rows is $2$, and clearly it cannot be made larger. ------------ **[Constraints and Scale]** | Test Point ID | $n \le$ | $tp=$ | |:-:|:-:|:-:| | $1$ | $3$ | $0$ | | $2 \sim 3$ | $7$ | $0$ | | $4$ | $3$ | $1$ | | $5$ | $4$ | $1$ | | $6$ | $5$ | $1$ | | $7 \sim 8$ | $6$ | $1$ | | $9 \sim 10$ | $7$ | $1$ | For all data, it is guaranteed that $1 \le n \le 7$, $1 \le T \le 3$, and $tp \in \{0, 1\}$. ------------ **[Hint]** - You may use the following statements to flush the buffer: - For C/C++: `fflush(stdout)`. - For C++: `std::cout