Problem C
Coins

You have been challenged by the infamous magician Zhivago to his signature coin game! The game starts off with a pile of $n$ coins, where you and Zhivago will each take turns grabbing coins from the pile, and the loser is the one that grabs the last coin. Each player has to take $1$, $2$ or $3$ coins each turn; no more, no less!

Zhivago is a master in his own game, and will always play optimally. However, you have been informed that you are in a winning position, and can best Zhivago to become the coin game champion. Can you do it?

Interaction

First, your program should read a single integer $ 1 \leq n < 1000$, the number of coins in the pile at the start of the game. Then, we repeat the following process:

• Your program writes a single line to the standard output, in the form of an integer $1$, $2$ or $3$ that represents the move you make.

• After you have made your move, then your program should read a single integer $c \in \{ 1, 2, 3\} $ representing how many coins Zhivago takes on his turn.

• If there is only a single coin left for Zhivago, he will output the string “I give up” instead. At this point your program should terminate.

After making each move, do not forget to flush the output. To do this, use:

• fflush(stdout) or cout.flush() in C++;

• System.out.flush() in Java;

• stdout.flush() or print(output, flush=True) in Python;

• see documentation for other languages.

Sample game