Background

This is an interactive problem.

Problem Description

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.

Input Format

See “Interaction Protocol”.

Output Format

See “Interaction Protocol”.

1 1
1

2

1

2

1

1

2

1

2

Hint

[Sample Explanation]

The input has $n = 1$, so the board size is $4 \times 2$. The two players simulate as shown in the 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]

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 << std::flush.
  • For Java: System.out.flush().
  • For Python: stdout.flush().
  • For Pascal: flush(output).
  • For other languages, please check the documentation of the corresponding language.
  • In particular, for C++, using std::endl instead of '\n' when printing a newline can also flush the buffer automatically.

• We guarantee that the interactive library runs within $1.5\text{s}$, and the memory usage can be ignored.

Translated by ChatGPT 5