F. Rocket Cycle
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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().

Bobob has developed a new and improved rocket cycle deck that exploits the overwhelming force of rockets to annihilate his opponents' towers. There's only one problem: he knows the enemy's two princess towers are horizontally aligned with each other, but he needs your help to find their exact x-coordinates.

In order to find the x-coordinates of the princess towers $$$x_1$$$ and $$$x_2$$$ ($$$1 \le x_1 \lt x_2 \le n$$$), you can place down hog riders. Each hog rider can be placed at an x-coordinate by printing a single integer from $$$1$$$ to $$$n$$$. Flush output stream after printing each x-coordinate. Hog riders will target the nearest tower (or the right tower if halfway in between), earning one of three possible responses:

  • the string "<" (without quotes), if the closest princess tower is to the left of the hog rider ($$$x_{tower} \lt x_{hog}$$$);
  • the string ">" (without quotes), if the closest princess tower is to the right of the hog rider ($$$x_{tower} \gt x_{hog}$$$);
  • the string "=" (without quotes), if the hog rider is on top of a princess tower ($$$x_{tower} = x_{hog}$$$).

The closest princess tower $$$x_{tower}$$$ is determined to be $$$x_1$$$ if $$$|x_{hog} - x_1| \lt |x_{hog} - x_2|$$$, and $$$x_2$$$ otherwise.

When you figure out the x-coordinates of the two princess towers, print string "! x1 x2", where $$$x1$$$ and $$$x2$$$ are the x-coordinates of the princess towers from left to right ($$$x1 \lt x2$$$), and terminate your program normally immediately after flushing the output stream.

You only have 500 elixir, and each hog rider costs 4 elixir, so you are allowed to place no more than 125 hog riders (not including printing the princess towers' coordinates at the end).

Input

Use standard input to read the responses to the hog riders.

The first line contains an integer $$$n$$$ ($$$2 \le n \le 10^9$$$) — the maximum possible x-coordinate.

The following lines will contain responses to your hog riders — strings "<", ">" or "=". The $$$i$$$-th line is a response to your $$$i$$$-th hog rider. When you are ready to guess the princess towers' coordinates, print "! x1 x2" and terminate your program.

The game will allow you to read the response to the hog rider only after your program prints the hog rider's x-coordinate and performs the flush operation.

Output

To print the hog riders' coordinates, your program must use standard output.

Your program must print the hog riders' x-coordinates — integer numbers $$$x$$$ ($$$1 \le x \le n$$$), one query per line (do not forget "end of line" after each $$$x$$$). After printing each line your program must perform the flush operation. When you are ready to guess the princess towers' coordinates, print "! x1 x2", flush, and terminate your program.

Examples
Input
10

<

=

>

=

Output

4

1

5

9

! 1 9
Note

In this example, the princess towers are located at x-coordinates $$$1$$$ and $$$9$$$.

Placing a hog rider at an x-coordinate of $$$4$$$ will result in it targeting the princess tower at $$$1$$$ because $$$|4-1| \lt |4-9|$$$, so the response is "<".

Placing a hog rider at an x-coordinate of $$$1$$$ will be on top of a princess tower, so the response is "=".

Placing a hog rider at an x-coordinate of $$$5$$$ will result in it targeting the princess tower at $$$9$$$ because $$$|5-9| \ge |5-1|$$$, so the response is ">".

Placing a hog rider at an x-coordinate of $$$9$$$ will be on top of a princess tower, so the response is "=".

The player correctly guesses that the princess towers are at x-coordinates $$$1$$$ and $$$9$$$, and the program terminates.