Strange Chess Dream

In a bizarre dream, Xiao X and Xiao Q are playing an unusual chess game on a board of size \(2^{2n}\times 2n\). Xiao X (black) moves first and Xiao Q (white) moves second.

The board has \(2^{2n}\) rows and \(2n\) columns. Moves are made in the current row that is not yet full. In every move, a player may place their piece in any vacant cell of the current (first incomplete) row. Once a row is filled (i.e. it contains exactly \(2n\) moves), the game moves on to the next row. After the board is completely filled, there are \(2^{2n}\) rows of pieces. The score for Xiao X is defined as the number of essentially distinct rows (i.e. rows which are not identical in an "essential" sense).

Xiao X wants to maximize her score while Xiao Q strives to minimize it. Moreover, if you are playing as Xiao X, in addition to maximizing the final score \(ans\), you must also maximize the number of essentially different rows among the first \(ans\) rows.

You are required to play as either Xiao X or Xiao Q, where your task is to maximize or minimize Xiao X's score accordingly.

---

Interaction Protocol

The first line of input contains two integers \(T\) and \(tp\), representing the number of test cases and the role you assume. It is guaranteed that \(tp \in \{0,1\}\). If \(tp = 0\), you play as Xiao Q (the second mover); if \(tp = 1\), you play as Xiao X (the first mover).

For each test case, the first line contains a positive integer \(n\). Then, the game proceeds via \(2^{2n} \times n\) rounds of interaction. In each round:

• If \(tp = 0\) (you are Xiao Q):
  • First, you read an integer \(x\) from the standard input. This is Xiao X’s move where she places a black piece in the \(x\)th column of the current incomplete row.
  • Then, you must output a positive integer \(y\) (followed by a newline and flushing the output) representing your response by placing a white piece in the \(y\)th column of the current incomplete row.
• If \(tp = 1\) (you are Xiao X):
  • First, you must output a positive integer \(x\) representing your move by placing a black piece in the \(x\)th column of the current incomplete row.
  • Then, you read an integer \(y\) from the standard input representing Xiao Q’s move where a white piece is placed in the \(y\)th column of the current incomplete row.

Your move must always be in an unoccupied cell. The interactive judge guarantees that the moves provided by the opponent are always in unoccupied positions. When a row is completely filled with \(2n\) moves, the game automatically continues on the next row.

Note: Although an optimal strategy is expected to maximize (or minimize) Xiao X's final score, for this problem you only need to ensure that all moves are valid with respect to the rules described above.

inputFormat

The first line of input contains two integers \(T\) and \(tp\). \(T\) is the number of test cases and \(tp\) indicates your role (0 for Xiao Q and 1 for Xiao X). For each test case, the first line contains a positive integer \(n\). The game then proceeds with \(2^{2n} \times n\) rounds of interaction as described in the problem statement.

outputFormat

During each interaction round, you must output a valid move (a positive integer denoting the column number in the current row, starting from 1). The output should be flushed after each move. Ensure that you never output a move to a cell that is already occupied.

sample

1 1
1

# For role tp=1 (Xiao X) with n=1. In an interactive simulation, your program should output a valid move, e.g., 1, then read an opponent move.

1

</p>