This is an interactive problem. You have to use a flush operation right after printing each line. For example, in C++ you should use the function fflush(stdout), in Java — System.out.flush(), in Pascal — flush(output), and in Python — sys.stdout.flush().

In this problem, the jury has some number $x$, and you have to guess it. The number $x$ is always an integer from $1$ to $n$, where $n$ is given to you at the beginning.

You can make queries to the testing system. Each query is a single integer from $1$ to $n$. Flush the output stream after printing each query. There are two possible responses the testing program can provide:

• The string < (without quotes), if the jury's number is less than the integer in your query.
• The string >= (without quotes), if the jury's number is greater than or equal to the integer in your query.

When your program guesses the number $x$, print the string ! x, where $x$ is the answer, and terminate your program normally immediately after flushing the output stream.

Your program is allowed to make no more than 25 queries (not including printing the answer) to the testing system.

Input

Use standard input to read the responses to the queries.

The first line contains an integer $n$ ($1 \leq n \leq 10^6$) — the maximum possible value of the jury's number.

Following lines will contain responses to your queries — strings < or >=. The $i$-th line is a response to your $i$-th query. When your program guesses the number, print ! x, where $x$ is the answer, and terminate your program.

The testing system will allow you to read the response to the query only after your program prints the query for the system and performs the flush operation.

Output

To make the queries, your program must use standard output.

Your program must print the queries — integer numbers $x_i$ ($1 \leq x_i \leq n$), one query per line (do not forget the newline character after each $x_i$). After printing each line, your program must perform the flush operation.

Each of the values $x_i$ represents a query to the testing system. The response to the query will be given in the input file after you flush the output. When your program guesses the number, print the string ! x, where $x$ is the answer, and terminate your program.

Example

Input:

20
<
>=
>=

Output:

5
3
4
! 4