Mirko has a hidden permutation $p_1, p_2, \dots, p_N$ of numbers from $1$ to $N$. His friend Slavko wants to discover the essence of Mirko's permutation, but Mirko will only answer questions of a specific form.

Slavko can choose any subsegment of the permutation, i.e., a segment $p_i, p_{i+1}, \dots, p_j$ ($1 \le i < j \le N$), and ask Mirko at which position the second largest number in that segment is located. Mirko then immediately answers with the requested position.

After answering all his questions, Mirko decided to test Slavko's knowledge. He will pose $Q$ queries of the same form, and he will expect a correct answer for each.

Slavko does not know Mirko's questions in advance, and to avoid angering him, he wants to ask as few questions as possible. Specifically, Slavko is allowed to ask Mirko at most $K$ questions. Help Slavko ask the questions and then answer Mirko's queries.

Interaction

This is an interactive task. Your program must establish a dialogue with the program created by the organizers.

At the beginning, your program must read the number $N$, the length of the permutation, from standard input.

Then it can send queries by printing to standard output. Each query must be printed on a separate line and have the form "? $i$ $j$", where $i$ and $j$ are natural numbers such that $1 \le i < j \le N$. The numbers $i$ and $j$ represent the boundaries of the subsegment for which Slavko wants to know the answer. Your program is allowed to ask at most $K$ such queries.

After each printed query, the program must flush the output and read the answer to the query from standard input — the position $k$ such that $i \le k \le j$.

When finished with asking its own questions, the program should print the character "!" to indicate the end of Slavko's questions and then flush the output.

After that, it is necessary to read the natural number $Q$ — the number of Mirko's queries. Then, read $Q$ queries, each in the form "$a$ $b$", where $a$ and $b$ are natural numbers such that $1 \le a < b \le N$. After reading all $Q$ queries, for each one, it is necessary to print the natural number $k$ — the position of the second largest element in the subsegment $p_a, \dots, p_b$.

After printing the answers to all queries, your program must flush the output. When it answers the last query, the program can terminate.

Subtasks

In all subtasks, $N \le 512$, $K = 2048$, and $Q = 2048$.

Examples

Input 1

4
? 1 2
2
? 1 3
1
!
2
1 4
2 3

Output 1

4
2
1
4
2