This is an interactive problem.

There are $n$ points on a number line with integer coordinates $x_1, x_2, \dots, x_n$. It is guaranteed that $1 \le x_i \le n$ for $1 \le i \le n$.

A point $x_k$ is considered to be between points $x_i$ and $x_j$ if and only if it belongs to the segment formed by points $x_i$ and $x_j$. Formally, a point $x_k$ is between points $x_i$ and $x_j$ if and only if $x_i \le x_k \le x_j$ or $x_j \le x_k \le x_i$.

You need to find any two indices $i$ and $j$ such that all $n$ points are between $x_i$ and $x_j$.

You can use the following query: choose three indices $(i, j, k)$ and determine whether the point $x_k$ is between the points $x_i$ and $x_j$.

You are allowed to use at most $22222$ queries.

It is guaranteed that the coordinates of the points are fixed before the interaction begins. In other words, the interactor is not adaptive.

Input

The first line contains a single integer $n$ ($3 \le n \le 2 \cdot 10^4$) — the number of points.

Interaction

To perform a query, output "? i j k" ($1 \le i, j, k \le n$), followed by a newline character, and then perform the flush operation.

In response to the query, the jury's program will output a single integer $f$ ($f \in \{0, 1\}$). If $f = 1$, then the point $x_k$ is between the points $x_i$ and $x_j$; if $f = 0$, then the point $x_k$ is not between them.

If the query is invalid (i.e., the maximum number of queries is exceeded or the query parameters are invalid), the jury's program will output -1 and terminate. In this case, terminate your program to receive a Wrong Answer verdict.

When you are ready to provide the answer, output it in the format "! i j" ($1 \le i, j \le n$), where $i$ and $j$ are the sought indices of the points. After this, terminate your program.

The flush operation is performed as follows:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• sys.stdout.flush() in Python.

Subtasks

1. (17 points): $n \le 20$;
2. (16 points): $n \le 100$;
3. (30 points): $n \le 10000$;
4. (23 points): $n \le 20000$, $x_i \le 2$;
5. (10 points): $n \le 12000$;
6. (4 points): no additional constraints.

Examples

Input 1

4
1
1

Output 1

? 1 4 2
? 1 4 3
! 1 4

Note

In the example, the points have coordinates $x = [1, 2, 3, 4]$.