Nim-Yum-Yum#12352
Sign in

Nim-Yum-Yum

1 second
256 megabytes
Medium

Cat Macros and kitty Manty eat alternately from several bowls. Each of them can eat any number of pieces of food from one of the bowls. Cat Macros is very smart, so he tries to eat in such a way that the last piece of food is his. Manty also wants to eat the last piece, but she still doesn't quite understand how to do it. Macros allows kitty Manty to choose who will start. Help Manty eat the last piece of food.

This is an interactive problem. This means that during testing, the jury's program (referred to as the interactor) will run alongside your solution. Your program needs to "communicate" with it according to the interaction protocol.

Interaction

First, your program must read the number N — the number of bowls with food.

In the next line, read the number of pieces of food a_i in each bowl, separated by spaces.

(0<N\le10, 0\le a_i\le1000, 1\le i \le N)

After this, your program must output a single number on a separate line: 1 if Manty (represented by your program making "moves") starts first, 0 if she extends the right of the first "move" to Macros.

If you sent 1, your "move" starts immediately, and if 0 — you read the information about Macros' "move" (for whom the interactor will communicate). The move information consists of a line with two natural numbers separated by a space: the first number is the bowl number (bowls are numbered starting from one), the second number is the number of pieces that the player whose move it currently is will eat from this bowl. After your program has made its move, move on to reading the interactor's response. If during reading Macros' move you receive zero as the bowl number, it means the check is complete, and your program must immediately terminate.

Attention! For the correct operation of the interactor, you cannot use "input-output accelerators," and you need to complete each move with a flush operation.

In different languages, the flush operation should be executed as follows:

fflush(stdout) or cout.flush() in C++ (you can also terminate the line with endl);
System.out.flush() in Java;
flush(output) in Pascal;
stdout.flush() in Python;

for all other languages, you need to refer to the documentation yourself.

Examples

Example

Input
1
10
Output
program  : 1
program  : 1 10
iteractor: 0 0

Example

Input
2
10 10
Output
program  : 0
iteractor: 1 5
program  : 2 5
iteractor: 1 3
program  : 2 3
iteractor: 1 1
program  : 2 1
iteractor: 1 1
program  : 2 1
iteractor: 0 0

Example

Input
3
4 5 6
Output
program  : 1
program  : 1 1
iteractor: 3 3
program  : 2 5
iteractor: 1 2
program  : 3 2
iteractor: 1 1
program  : 3 1
iteractor: 0 0

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Note

In the first example, the program chooses to go first and takes all the pieces from the only bowl.

In the second example, the program grants the first move to the interactor. The interactor and program take five pieces each from the first and second bowls respectively, then three each, one each, and finally take one each again (the program takes the last piece).

In the third example, the program again chooses to go first:

  • The program takes 1 piece from the 2nd bowl (leaving 3 5 6)

  • The interactor takes 3 pieces from the 3rd bowl (leaving 3 5 3)

  • The program takes 5 pieces from the 2nd bowl (leaving 3 0 3)

  • The interactor takes 2 pieces from the 1st bowl (leaving 1 0 3)

  • The program takes 2 pieces from the 3rd bowl (leaving 1 0 1)

  • The interactor takes 1 piece from the 1st bowl (leaving 0 0 1)

  • The program takes 1 last piece from the 3rd bowl (leaving 0 0 0)