Neutron Decay Game

Youyou and Xiao Z are playing a game with \(n\) neutrons fixed in positions \(1 \sim n\). Initially, all positions contain a neutron which has not yet decayed.

Xiao Z owns a Weak Action Decay Machine (Wadm) that can decay a neutron into an electron (\(-1\)) or a proton (\(1\)). On each move, a player selects a neutron at a legal position (position that has not yet been decayed) and decays it into an electron or a proton. However, if after any move an electron and a proton become adjacent, the strong Coulomb attraction will cause them to leave the system, rendering that move illegal.

Special rule: If at the end all neutrons have been decayed into the same type (all electrons or all protons), then the second player wins regardless of who made the last move.

The interaction begins by reading two integers \(n\) and \(task\_id\). Your program must then decide whether to play first or second by outputting a single integer \(order\) (0 for first move, 1 for second move). Then, depending on the turn order, interact with your opponent as follows:

• If it is your turn, output two integers \(place\) and \(type\), where \(place \in [1, n]\) indicates the neutron position to decay and \(type\) is either \(-1\) (for electron) or \(1\) (for proton). Remember to flush the output buffer after printing your move.
• If it is your opponent's turn, read two integers \(place\) and \(type\) representing their move.

If no legal moves remain on your turn, you lose. Also, note that after the game ends, your program should immediately terminate to avoid any extra output.

inputFormat

The input consists of two integers \(n\) and \(task\_id\), where \(n\) is the number of neutrons and \(task\_id\) is the subtask identifier.

outputFormat

First, output an integer \(order\) (0 to play first, 1 to play second). Then, engage in an interactive protocol: on your turn, output two integers \(place\) and \(type\) (with \(type\) being either \(-1\) for an electron or \(1\) for a proton) after ensuring that the chosen neutron at position \(place\) is legal to decay. Flush your output after each move. When the game ends, the program should terminate immediately.

sample

3 1

0
1 1