mere

Ana and Barbu picked N apples, placed them on the table and now they have to get them ready to make compote. Seeing as cutting apples is usually a very boring task, they invented the following game. In their game they move alternatively, starting with Ana. The player that is moving has to execute one of the following 3 moves:
1. Cut an apple in three equal parts.
2. Cut an apple in two equal parts.
3. Cut an apple half in two equal parts.
The one who can't execute any more moves loses.

Task

Write a program that determines if Ana has a sure win strategy (irrespective of how Barbu plays, she can win the game). If this is possible, program all of Ana's moves, with Barbu's moves being read from the keyboard.

Input Data

The program doesn't read data from any file.

Output Data

The program won't write data to any file.

Interaction

Our program will interact with a commission program running in parallel. For each test-case your program will have to solve a series of tests. For each test case the interaction has the following format:
1. Your program reads a line from standard input, containing the number of apples N; if N is zero, it means that the test-case is complete and the program must end.
2. If N is not zero, your program will determine if Ana has or doesn't have a sure win strategy. If she does, your program will execute a number of rounds. A round consists of writing a line to standard output, which describes the move Ana executes in that round (the line will contain the number of the move, 1, 2 or 3). Then, a line will be read from standard input describing the move Barbu executed (the line will contain the number of the move executed, 1, 2 or 3). When your program has executed the last move, it displays a special line, containing only the word DONE
3. If your program has decided that Ana doesn't have a sure win strategy it will display a line containing value 0. Then it will display a line containing the word DONE

Scoring

Your program will be scored for the current test-case only if it correctly solved all the tests contained in that test-case.
Your program receives 0 points for a test in the following cases:
- during a round, it displays the number of a move that cannot be executed at that time;
- it displays that Ana has a sure win strategy when she doesn't (or vice-versa);
- when Ana has a sure win strategy, your program doesn't win;
- the display format for the problem is not respected.

Programming Instructions

C/C++ programmers must execute flush after they finished writing a complete line to output. This is also valid for the line containing DONE

For programs written in C++ using iostreams, the following sequence will be used for reading from standard input and writing to standard output:
cin>>x;
cout<<op<<'\n'<<flush;

For programs written in C using scanf and printf, the following sequence will be used for reading from standard input and writing to standard output:
scanf ("%d", &x);
printf("%d\n",op); fflush (stdout);

For programs written in Pascal the following sequence will be used for reading from standard input using readln, and for displaying a line writeln will be used:
readln(x);
writeln(op);

Constraints

• 1 <= n <= 1000
• In a test-case there are no more than 5 tests.
  

Time limit: 0.2 seconds/test

prof. Emanuela Cerchez
"Grigore Moisil" Iaşi IT High School
Contact:emanuela.cerchez@gmail.com