This is an interactive problem.

Hanburmi has a permutation $A$ of length $N$. In other words, $A$ is a sequence in which each integer from $1$ to $N$ appears exactly once. From the permutation $A$, which is only known to Hanburmi, you are asked to find the index $x$ such that $A_x = \left\lfloor \frac{N}{2} \right\rfloor + 1$. To do so, you may ask Hanburmi up to $10^4$ queries of the following type.

For each query, you choose a permutation $p$ of length $N$. Hanburmi then considers a histogram $H$ in which the height of the $i$-th bar is $A_{p_i}$. Among all rectangles that are completely contained in $H$ and whose base is parallel to the bottom of the histogram, Hanburmi finds one with the maximum area. If there are multiple rectangles with the maximum area, Hanburmi chooses any one of them with the greatest height. If the chosen rectangle spans from the $l$-th bar to the $r$-th bar and has height $h$, Hanburmi responds with three integers $l$, $r$, and $h$.

Interaction

Your program should interact with the interactor through standard input and standard output as follows.

First, the integer $N$ is given.

By printing the query below, you will receive a response on the next line with three integers $l$, $r$, and $h$, separated by spaces. You may use this query at most $10^4$ times.

• ? $p_1$ $p_2$ $\cdots$ $p_N$ (where $p$ is a permutation of length $N$)

You can submit the answer by printing the following query. This query does not count as a question, and the program must terminate immediately after printing.

• ! $x$ (where $1\le x\le N$)

The interactor is non-adaptive. In other words, the permutation $A$ is fixed before the interaction begins and does not change during the interaction.

For each test case, if the submitted answer is correct, you will receive Accepted; if it is incorrect, you will receive Wrong Answer. However, unexpected results may happen if you do not print the solution through proper interactions in the limitations of the problem provided.

Constraints

• $3\le N\le 50$
• $1\le l\le r\le N$
• $1\le h\le N$

Scoring

Examples

Input 1

3

1 2 2

1 1 3

1 2 2

Output 1

? 1 2 3

? 1 3 2

? 2 1 3

! 2

Note

In Example 1, this is an example where $A_1=3, A_2=2,$ and $A_3=1$.

A histogram is a shape composed of several rectangles aligned along the bottom. Each rectangle has a fixed width of $1$, but the heights may differ. For example, the following figure shows a histogram consisting of rectangles with heights $3, 5, 8, 8, 4,$ and $7$.

You must flush the output immediately after printing something. To flush you can use:

• C --- fflush(stdout)
• C++ --- std::cout.flush()
• Python --- sys.stdout.flush()
• Java --- System.out.flush()
• read the documentation for other languages.

Also, note that the empty lines in the example input and output are for the sake of clarity, and do not occur in the real interaction.