“When Gregor Samsa woke up one morning from restless dreams, he found himself transformed in his bed into a giant insect”... this is the translation of the famous first sentence of Kafka’s novel The Metamorphosis: “Als Gregor Samsa eines Morgens aus unruhigen Träumen erwachte, fand er sich in seinem Bett zu einem ungeheueren Ungeziefer verwandelt.”

It is little known that a small trick, a joke, was lost in the translation from German. Google Translate translates the above sentence without the last word verwandelt (German: transformed) essentially as: “When Gregor Samsa woke up one morning from restless dreams, he noticed a giant insect in his bed.” Thus, the reader remains surprised by the end of the first sentence and suddenly enters in medias res into what was then a new type of novel of the absurd.

But let us leave linguistic nonsense aside. Gregor is now an insect and is located at point $P_0$ in the plane. He is interested in whether he is inside the $N$-gon $P_1P_2 \dots P_N$.

It is known that insects have no sense other than an intrinsic sense for CCW (counterclockwise) orientation. Thus, Gregor can ask whether any three points $P_a, P_b, P_c$ are in CCW order.

The polygon $P_1P_2 \dots P_N$ is not necessarily convex, but it does not intersect itself. The points $P_0, P_1, \dots, P_N$ are distinct, and no three are collinear.

Definition: Points $A, B, C$ are in CCW order if point $C$ is on the left side of the line $AB$, looking from point $A$ towards point $B$.

Points $A, B, C$ in the left image are in CCW order, while in the right image they are not.

Interaction

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

Before the interaction, your program must read from standard input a natural number $N$ (the number of vertices of the polygon) and a natural number $Q$ (the number of queries your program is allowed to send).

After that, your program can send queries by writing to standard output. Each query should be printed on a separate line and take the form “? $a$ $b$ $c$”, where $0 \le a, b, c \le N$. After each printed query, your program must flush the output and read the answer to the query from standard input – the number 1 if the points $P_a, P_b, P_c$ are in CCW order, or 0 if they are not. Specifically, the answer will be 0 if the indices $a, b, c$ are not mutually distinct. Your program may send at most $Q$ such queries.

When your program has determined the answer, it should print “!1” to standard output if point $P_0$ is inside the polygon, or “!0” if point $P_0$ is outside the polygon. Then the program must again flush the output and terminate execution.

Note: Through the evaluation system, you can download example source codes that perform the interaction correctly, including flushing the output.

Subtasks

Examples

Input 1

5 125
1
1
0
0

Output 1

? 1 2 3
? 0 4 1
? 2 5 4
? 0 1 5
! 0