Mirko has hidden a tree with $N$ nodes from Slavko. Slavko is very interested in what Mirko's tree looks like, but the only thing he knows is that the degree of each node in the tree is at most 3, i.e., every node has at most three neighbors.

Mirko felt sorry for Slavko and allowed him to ask $K$ questions about the tree. For a given triple of distinct nodes $a$, $b$, and $c$, Mirko will answer: 0 if the distance between nodes $a$ and $b$ is equal to the distance between nodes $a$ and $c$ 1 if the distance between nodes $a$ and $b$ is less than the distance between nodes $a$ and $c$ * 2 if the distance between nodes $a$ and $b$ is greater than the distance between nodes $a$ and $c$.

The distance between nodes $u$ and $v$ is defined as the number of edges on the path between them.

Help Slavko determine Mirko's tree!

Interaction

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

At the beginning, your program should read the number $N$, the size of the tree, 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 "? $a$ $b$ $c$", where $a$, $b$, and $c$ are natural numbers such that $1 \le a, b, c \le N$ and $a \neq b$, $b \neq c$, and $c \neq a$. The numbers $a$, $b$, and $c$ represent the nodes of the tree for which Slavko wants to know the answer. Your program may ask at most $250\,000$ such queries.

After each printed query, the program must flush the output and read the answer to the query from standard input — a non-negative number $k$ such that $k \in \{0, 1, 2\}$.

When it finishes asking its queries, 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 print the edges of Mirko's tree. That is, print $N - 1$ lines where the $i$-th line contains a pair of numbers $u_i$ and $v_i$, which represent an edge in Mirko's tree. The order of nodes in an edge and the order of edges in the output do not matter. It is necessary to print all edges.

After printing the answer, your program should flush the output and terminate execution.

Subtasks

In all subtasks, $N < 512$.

Let your program achieve a solution in at most $K$ queries in a given subtask. The number of points for that subtask will then be:

$$\min \left( 1, \left( \frac{14000}{K} \right)^{0.7} \right) \cdot B$$

where $B$ is the number of points for the subtask. Only queries of the form "? $a$ $b$ $c$" are counted.

Examples

Input 1

4

Output 1

? 1 2 3

Input 2

1

Output 2

? 1 4 3

Input 3

2

Output 3

? 2 1 3

Input 4

0

Output 4

!
1 2
2 3
3 4

Note

Suppose Mirko's tree has edges (1, 2), (2, 3), and (3, 4).