H. No More Than Two in a Row
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

The playing field is a strip one cell wide and $$$n$$$ cells long. Two players take turns making moves. On each move, an empty cell is chosen and marked with a cross. It is forbidden for the field to contain more than two consecutive crosses. The player who has no legal move loses.

Write a program that plays against the jury's program. Your program must win all rounds. This is always possible, since you choose who makes the first move.

Interaction

First, input an integer $$$n$$$ ($$$1 \le n \le 30$$$) — the length of the strip.

Next, decide who makes the first move. Output 1 if you move first; otherwise output 2. Then output a newline and flush the standard output buffer.

After that, your program must repeatedly do the following.

  • If it is your turn, output one integer from $$$1$$$ to $$$n$$$ — the cell where you place a cross. Then output a newline and flush the standard output buffer. If there is no legal move, output 0 and terminate the program.
  • If it is the opponent's turn, input one integer from $$$0$$$ to $$$n$$$. If the input number is greater than zero, then it is the cell where the opponent moved. If the input number is 0, then the game is over — terminate the program.

Example input-output:

InputOutput
4
1
4
2
1
0

Note

To flush the buffer use:

  • cout.flush(); or cout << flush; or cout << endl; — for C++ (the latter will also output a newline)
  • fflush(stdout); — for C or C++ with the old output style
  • sys.stdout.flush() — for Python (you need to import the sys module)
  • System.out.flush(); — for Java
  • Console.Out.Flush(); — for C#
  • flush(output); — for Pascal