Stolen Helmet

For the past months you've been investigating the theft of the Golden Helmet of Coțofenești. You managed to narrow down the list of possible hiding spots down to $N$ locations, but can't make further progress, so you resort to the help of Mob, a psychic with supernatural abilities.

Task

You can give your friend Mob 2 locations amongst the $N$ on the list and he will use his psychic abilities to tell you if the stolen helmet is closer (measured by Euclidean distance) to the 1st or the 2nd location. However, great power comes with great energy consumption, so he needs a whole day of rest after each search. Since you want to solve the case as soon as possible you'll need to make good use of Mob's powers.

Input data

The first line contains the only integer $N$. The next $N$ lines contain $2$ integers each: $X_i$ and $Y_i$ - the coordinates of the $i$-th location.

Output data

This is an interactive task. To ask Mob a question print "? $i$ $j$" on a new line where $0 \le i, j \le N-1$ are indices of two locations on the list. Mob will then respond with $0$ if the Euclidean distance from the $i$-th location to the helmet is less than or equal to the Euclidean distance from the $j$-th location to the helmet, or $1$ otherwise. When you know the location print "! $i$" where $0 \le i \le N-1$ is the index of the location.

The output must be flushed after every interaction. In C++ this can be done by using cout.flush(). If you ever read $-1$ from the input stream end the execution immediately.

Constraints and clarifications

• $2 \le N \le 100 \ 000$.
• $-10^9 \le X_i, Y_i \le 10^9$ for each $i=0\ldots N-1$.

Your program will be tested against several test cases grouped in subtasks.

In order to obtain the full score for a test your program must identify the location in at most 30 queries. Using more than 30 queries will result in a lower score equal to $\frac{30}{\text{queries used}}$.

Example

stdin

6
0 0
-2 0
-4 0
2 2
2 -2
5 1

0

1

0

stdout

? 2 5

? 0 1

? 1 2

! 1

Explanation

In the first sample case it can be verified that P1 is the only point that's closer to point 2 than to point 5, closer to point 1 than to point 0, and closer to point 1 than to point 2.