Bread Selection Game

There are 9 breads arranged in a row, where the i-th bread has a weight of i (1 ≤ i ≤ 9). Two players take turns choosing one bread at a time. Once a bread is chosen it cannot be chosen again. The first player whose set of chosen breads contains any three breads that sum up exactly to \(15\) wins immediately. If all breads are chosen without either player achieving this condition, the game is a draw.

The interaction protocol is as follows:

• Before the games start, your function init() is called exactly once to allow you to perform any initializations. (Even if you do not need any initialization, the function must be provided.)
• Before each new game, the judge calls newgame(bool f) where f is a boolean; if f is true (or 1), it means the judge (opponent) makes the first move; otherwise, you make the first move. Note that when you are to move first, the judge will call your choose(int x) function with x = 0 to indicate that it is your turn.
• After that, the judge calls the function choose(int x) repeatedly to communicate the opponent's move. Here, x represents the index (1-based) of the bread chosen by the opponent. When your choose function is called, it must return the index (between 1 and 9) of an available bread. If you return an invalid move (e.g. a bread that has already been taken or an index outside of 1 to 9), you lose the game immediately.
• This process continues until one player wins (by obtaining any triple of breads with a sum exactly equal to \(15\)) or the game ends in a draw if all breads have been selected without a win for either side.
• The judge will conduct a total of 1800 games by repeatedly calling newgame(bool f).

Note: It is recommended that you use C++ to solve this problem.

Functions to implement (do not remove the extern "C" specifier in C++):

extern "C" int choose(int x);
extern "C" void init();
extern "C" void newgame(bool f);

You are allowed to implement additional helper functions if necessary.

inputFormat

There is no traditional input for the problem. Instead, a judge will call the functions init(), newgame(bool f), and choose(int x) in an interactive manner as described above.

outputFormat

There is no traditional output. Your functions must return valid moves (the index of a bread) when called. If an invalid move is returned, the judge will consider the game lost.

sample

0

1