Description

There are $n$ neutrons in front of Youyou and Xiao Z, arranged in a line from left to right. These neutrons are fixed by the strong force at positions numbered $1 \sim n$.

Xiao Z has a weak-interaction decay machine Wadm (Weak Action Decay Machine). Each time, Wadm can cause one neutron to undergo weak decay, releasing an electron and a proton (neutrinos are ignored in this problem). Then, according to Youyou's or Xiao Z's instruction, Wadm keeps one of the two particles and removes the other from the system.

In short, Wadm can turn one neutron into an electron or a proton.

Now Xiao Z wants to play a game with Youyou: they take turns using Wadm to operate on one neutron, turning it into an electron or a proton. However, if an electron and a proton are adjacent, then due to the strong Coulomb attraction, they will break free from the strong-force constraint, so this situation is not allowed. If it is someone's turn and no position can be operated anymore, then that person loses.

Youyou happily agrees to Xiao Z's request, but facing the clever Xiao Z, Youyou has to ask you for help.

In particular, if all neutrons eventually become the same kind of particle, then the second player wins.

If you help Youyou defeat Xiao Z, Youyou will give you a Wadm as a reward!

Interaction

Your program should read from standard input and write to standard output.

The input contains two integers n task_id, representing $n$ in the statement and the subtask id.

Then you need to output an integer order. $\text{order}$ can only be $0$ or $1$. $0$ means you choose to move first, and $1$ means you choose to move second.

Next, you should interact with the interactive library through standard input/output according to whether you move first or second.

• If it is your turn, you should output two integers place type, meaning you turn the neutron at position $\text{place}$ into an electron ($\text{type}=-1$) or a proton ($\text{type}=1$). You must ensure that:

  • $\text{place} \in [1,n]$ and that position is operable;
  • $\text{type} \in \{-1,1\}$;
  • you have flushed the output buffer. In C or C++, you may use fflush(stdout). In C++, you may also use cout << flush, cout.flush(), or print a newline using endl instead of '\n'.

• If it is Xiao Z's turn, you should read two integers place type, meaning Xiao Z turns the neutron at position $\text{place}$ into an electron ($\text{type}=-1$) or a proton ($\text{type}=1$). It is guaranteed that:

  • $\text{place} \in [1,n]$ and that position is operable;
  • $\text{type} \in \{-1,1\}$.

For example, if you choose to move first, you should interact in the order “output, input, output, input, ...”. If you choose to move second, you should interact in the order “input, output, input, output, ...”.

Note that if the game ends, you should terminate the program immediately. Extra output after the game ends may cause RE.

Input Format

See “Interaction”.

Output Format

See “Interaction”.

4 1


2 1

0
1 1

4 -1

Hint

• Subtask 1 (5 points): $n \leq 4$.
• Subtask 2 (8 points): $n \leq 8$.
• Subtask 3 (12 points): $n$ is even, special strategy of the interactive library*.
• Subtask 4 (15 points): special strategy of the interactive library*.
• Subtask 5 (20 points): $n$ is even.
• Subtask 6 (40 points): no special constraints.

*Special strategy of the interactive library: each time it is the interactive library's turn, it finds the leftmost position that can be operated, and then if that position can be operated into a proton, it operates it into a proton; otherwise, it operates it into an electron.

For all testdata, it is guaranteed that $1 \leq n \leq 2^{10}$.

Translated by ChatGPT 5