Problem

Play Nim against the judge and win.

Problem Statement

This is a reactive problem.

You are given an integer $n$ and an integer sequence $a$ of length $n$.

The game is played by two players: the judge and you. You can choose whether to go first or second. The first player moves first, then the second player moves, and they continue to move alternately. One move is the following series of operations.

1. Choose $1$ integer $i$ satisfying $1 \le i \le n$ and $a_i \neq 0$. If no such $i$ exists, the player loses and the game ends.
2. Choose an integer $k$ satisfying $1 \le k \le a_i$, and replace $a_i$ with $a_i -k$.

Since the game ends after a finite number of operations, repeating moves always results in a player who loses, and the player who has not lost wins.

Win the game.

About evil cases

In this problem, the constraints are kept small because of the speed of the reactive judge, but evil cases (see here, under "Policy on judging correct answers") are included to distinguish fast solutions.

For these cases, even a fast solution may not be guaranteed to get AC, depending on the language and implementation. (This does not affect the judge result.)

Constraints

• $1 \le n \le 10^4$
• $1 \le a_i \le 10^4$
• $\sum_{i=1}^{n} a_i \le 10^4$
• All input and output values are integers.

Constraints for evil cases

• $1 \le n \le 7.5 \times 10^4$
• $1 \le a_i \le 7.5 \times 10^4$
• $\sum_{i=1}^{n} a_i \le 7.5 \times 10^4$
• All input and output values are integers.

Input and Output

First, an integer $n$ is given.

$n$

Then, $n$ integers are given.

$a_1\ a_2\ \dots\ a_n$

Next, you choose whether to go first or second.

$t$

Here, you must have $t=1$ if you choose to go first, and $t=0$ if you choose to go second. After that, moves are repeated until the game ends.

On your move, you must choose integers $i, k(1 \le i \le n, 1 \le k \le a_i)$ and output them.

$i\ k$

This means that you made the move of replacing $a_i$ with $a_i - k$.

After that, an integer $ret$ is given.

$ret$

Here, if $ret=0$, the game continues; if $ret = -1$, terminate your program immediately.

On the judge's move, you are given integers $i, k(1 \le i \le n, 1 \le k \le a_i)$.

$i\ k$

This means that the judge made the move of replacing $a_i$ with $a_i - k$.

After that, an integer $ret$ is given.

$ret$

Here, if $ret=0$, the game continues; if $ret = -1$, terminate your program immediately.

Notes

• Once the judge's victory is determined under the assumption that the judge plays optimally, the judge may send the program termination signal ($ret=-1$) even if the game has not ended.
• Print a trailing newline and flush after each output.
• The judge's behavior for invalid output or behavior may be undefined.

Sample