G. Cars and Dirty Socks
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem. If you are not familiar with this type of problem, it is recommended to read the following guide: https://codeforces.me/blog/entry/45307

Kaladin is participating in a game by the famous YouTuber Mr. Besta. The game works as follows:

  • There are 3 doors numbered from 1 to 3.
  • Behind one of the doors, there is a new car, and behind the other two, there is a dirty sock. The door with the car is chosen randomly.

The host of the game challenges Kaladin to guess which door hides the car. The game follows these steps:

  • Kaladin initially chooses one of the 3 doors.
  • The host opens one of the remaining doors, revealing a dirty sock.
  • Kaladin has the option to stick with his initial choice or switch to the other closed door.
  • Finally, the door chosen by Kaladin is opened, and he finds out if he won the car.

Kaladin will participate in the game $$$N=10000$$$ times in a row. He will only win the car if he guesses correctly at least $$$6500$$$ out of the $$$N$$$ games. Your task is to implement a strategy to help Kaladin win the car.

This is an interactive question. Remember to always "flush" the output with "std::endl" or cout.flush()

Input

The input is interactive and follows this format:

  • In the first line, you will receive an integer $$$N = 10^4$$$, indicating the number of times Kaladin will play.
  • For each game:
    • You must print an integer between 1 and 3, representing the initially chosen door.
    • You will receive an integer between 1 and 3, indicating the door opened by the host with a dirty sock.
    • You must print another integer between 1 and 3, representing the door chosen by Kaladin as his final decision.
    • You will receive an integer $$$0$$$ or $$$1$$$, where $$$1$$$ means Kaladin won the car, and $$$0$$$ means he chose a dirty sock.

Note that there is only 1 test case, so there is no test input!

Output

You should not produce direct standard output, except for the interaction with the system described in the input section. Your strategy will be evaluated at the end. Kaladin will win the car if he guesses correctly at least $$$6500$$$ times in $$$N = 10000$$$ games.

Interaction

For example, suppose there is only $$$1$$$ test case and the game occurred as follows:

  • Kaladin chooses door $$$1$$$
  • It is revealed that door $$$2$$$ has a sock
  • Kaladin chooses door $$$1$$$ as his final decision
  • It is revealed that he guessed correctly (1 is written in the Input)

Input/Judge 


1
2
1

Kaladin: 


1
1
Note
  • The host will always open a door with a dirty sock, among those that Kaladin did not choose (that is, a door that was not chosen by Kaladin and that does not contain the car).
  • Use an efficient strategy to maximize Kaladin's chances of winning the car.

It is guaranteed that there is only $$$1$$$ test case, and that the input is random.