Faulty Guessing Game

The judging machine randomly selects an integer \( x \) from the interval \( [1,n] \) with equal probability. Your task is to guess this hidden number.

You may ask at most \( q \) queries. In each query, you must output an integer \( y \) from \( [1,n] \) and then flush the output immediately. After each query, you will receive a response from the judging machine according to the following rules:

• If \( y = x \), the machine returns '='.
• If \( y \neq x \) and the current query is the \( q \)th query, the machine returns '!' and you must stop querying.
• If \( y > x \), then with probability \( \frac{100-p}{100} \) the machine returns '>' and with probability \( \frac{p}{100} \) it returns '<'.
• If \( y < x \), then with probability \( \frac{100-p}{100} \) the machine returns ''.

Note: Once you receive either '=' or '!', you must stop making further queries.

Flush Instructions: Remember to flush the output buffer after each query. For example, in C/C++ use fflush(stdout) or std::cout << std::flush, in Java use System.out.flush(), in Python use stdout.flush(), and so on.

This is an interactive problem; however, for the purpose of this contest, the input will be provided in a single line containing four numbers, and your program should output the hidden number \( x \) immediately.

inputFormat

The input consists of a single line containing four space-separated integers:

1. \( n \): the upper bound of the range \( [1,n] \) (\( 1 \le x \le n \)).
2. \( x \): the hidden integer selected by the judging machine.
3. \( q \): the maximum number of queries allowed.
4. \( p \): the error probability percentage (\( 0 \le p \le 100 \)).

For example: 10 7 5 0

outputFormat

Output the guessed number, which is exactly the hidden integer \( x \).

sample

10 7 5 0

7