Background

This is an interactive problem.

The checker contains the official solution, so it is not provided.

Problem Description

Two players, A and B, are playing a game. They take turns operating on a pair of integers $(x, y)$.

Initially, $(x, y) = (1, 0)$. There are three possible operations:

1. Change $(x, y)$ to $(1, x + y)$.
2. Change $(x, y)$ to $(2x, y)$.
3. Change $(x, y)$ to $(3x, y)$.

A positive integer $n$ is given. When $x + y \ge n$, the last two operations cannot be performed. If after a player makes a move, $y \ge n$, then that player loses.

It is guaranteed that the given $n$ is a winning position for the first player. You need to provide a winning strategy for the first player. For example, when $n = 3$, the first player chooses operation 3. Then the second player can only choose operation 1 and loses, so the first player wins for $n = 3$.

Interactive problem. You need to implement a function extern "C" int _opt(int n, int x, int y). The return value of this function is an integer equal to $1$, $2$, or $3$, indicating which operation you will choose when the current pair is $(x, y)$, the parameter is $n$, and it is your turn.

Hint

Constraints

For all test points, it is guaranteed that $1 \le n \le 30000$.

Notes

A sample interaction library is provided in the attachment. After compiling it locally together with the contestant program, you can use standard input to simulate the interaction between the special judge (spj) and the contestant program.
When the interaction library outputs -2 -2 and exits, it means the contestant program is correct.

Translated by ChatGPT 5