401737: GYM100519 I Interactive Primes Guessing

The jury has chosen the numbers X₀ and P (1 ≤ X₀ < P ≤ N, P is a prime number). You are given the number N: the upper limit for P.

Your task is to guess the number P.

In order to do that, your program will ask the questions in the form of A_i (2 ≤ A_i ≤ N, A_i is a prime number) where i = 1, 2, ... is the index of the question.

After each question, the answer comes. In case the i-th question does not guess the number P, the jury calculates and returns your the result of comparison of X_i and X_i - 1 (">", "<" or "=").

Your program must guess the number P by asking not more than 42 questions.

The first line of input contains a single integer N (2 ≤ N ≤ 3·10⁵). The answers for the questions of your program are given on separate lines.

If the i-th question is the number P, then the string "OK" is given as an answer. In other cases, the result of comparison between X_i and X_i - 1 is returned. If X_i > X_i - 1 then the answer is ">", if X_i < X_i - 1 then the answer is "<", otherwise the answer is "=".

After receiving the answer "OK", your program must stop sending questions.

Your program must output a single question on a separate line. Each question must consist of a single prime number A_i (2 ≤ A_i ≤ N).

100
<
>
>
>
>
>
OK

29
43
23
17
29
17
73

Among all possible pairs (X₀, P) where P ≤ 100, only the pair (41, 73) satisfies the following equations for the questions given in the first example test: X₁ < X₀, X₂ > X₁, X₃ > X₂, X₄ > X₃, X₅ > X₄, X₆ > X₅ (X₀ = 41, X₁ = 21, X₂ = 27, X₃ = 37, X₄ = 45, X₅ = 64, X₆ = 66).

The pipe from your program to the interactor program and the pipe back have limited size. Your program must read from the standard input to avoid deadlock. Deadlock condition is reported as "Time Limit Exceeded".

To flush the standard output stream, use the following statements:

In C, use fflush(stdout);

In C++, use cout.flush();

In Java, use System.out.flush();

In Python, use sys.stdout.flush().

If your program receives an EOF (end-of-file) condition on the standard input, it MUST exit immediately with exit code 0. Failure to comply with this requirement may result in "Time Limit Exceeded" error.