Background

Little $\mathfrak{f}$ and little $\mathfrak{g}$ are playing a number guessing game, but because the wind is too loud, they cannot hear what the other person says clearly.

Problem Description

The judge randomly selects an integer $x$ uniformly from the interval $[1,n]$. Your task is to guess this number.

Each time, you may give an integer $y$ in $[1,n]$ and ask for the comparison between $y$ and $x$. You can ask at most $q$ times.

However, for some reason, the judge has a $p\%$ probability of making a mistake.

Specifically:

• If $y=x$, then the judge returns =.
• If $y\ne x$, and this is already the $q$-th query, then the judge returns !.
• After getting either of the above two results, you should stop querying.
• If $y>x$, then with probability $(100-p)\%$ the judge returns >, and with probability $p\%$ it returns <.
• If $y<x$, then with probability $(100-p)\%$ the judge returns <, and with probability $p\%$ it returns >.

For each query, you need to output an integer in $[1,n]$ to standard output, and then flush the buffer.

You may use the following statements to flush the buffer:

• For C/C++: fflush(stdout);
• For C++: std::cout << std::flush;
• For Java: System.out.flush();
• For Python: stdout.flush();
• For Pascal: flush(output);
• For other languages, please check the corresponding language documentation yourself.

In particular, for C++, if you output a newline using std::endl instead of '\n', it can also flush the buffer automatically.

Then you need to read a character from standard input, which represents the result returned by the judge.

Input Format

Before you start querying, one line with three integers $n,p,q$ separated by spaces.

For each query, one line with one character, which must be one of =, !, >, <.

Output Format

For each query, output one line with one integer in $[1,n]$.

100 0 10

>

<

=

50

25

37

100 10 10

<

<

=

50

25

37

100 0 2

>

!

50

25

Hint

Explanation for Sample $1$:

At this time, the status of this test point is AC.

Explanation for Sample $2$:

When $x=37,y=50$, we have $y>x$. There is a $10\%$ probability to output <, and it happened to output <.

Explanation for Sample $3$:

At this time, the status of this test point is WA.

This problem uses bundled testdata.

Each Subtask contains $5$ test points. You only need to pass at least $3$ of them to get the score for that Subtask.

This problem does not use subtask dependencies.

For all testdata, $n=10^{18}$.

Constraints

Translated by ChatGPT 5