Background

Translated from Izborne Pripreme 2021 (Croatian IOI/CEOI Team Selection) D1T2. $\texttt{3s,0.5G}$。

As everyone knows, insects can only sense clockwise and counterclockwise directions.

If you suspect the SPJ is incorrect, please contact the problem porter. SPJ code。

Problem Description

This is an interactive problem.

On a 2D plane, there is a polygon $P$ with $N$ points. Note that $P$ is not necessarily convex (it can be concave). We number the points on the polygon in order from $1$ to $N$.

In addition, there is an extra point $0$. Determine through interaction whether it is inside $P$.

It is guaranteed that the polygon edges do not intersect. It is guaranteed that these $(N+1)$ points are pairwise distinct. It is guaranteed that no three points are collinear.

Definition: $A, B, C$ are in counterclockwise order if and only if, when looking from $A$ to $B$, point $C$ is on the left side of the line $AB$, as shown in the left figure.

【Implementation Details】

Before the interaction starts, you need to read a line with two integers $N, Q$, representing the number of vertices of the polygon and the maximum number of queries allowed.

Then, your program interacts with the interactive library through standard input/output. The following queries are allowed:

• $\texttt{? a b c}$: Ask whether points $a, b, c$ are in counterclockwise order. You must ensure that $a, b, c$ are pairwise distinct, and that $0 \le a, b, c \le N$.

  If $a, b, c$ are in counterclockwise order, the answer is $1$; otherwise, the answer is $0$.

After you determine the answer, output it in the following format:

• $\texttt{! x}$: If $x = 1$, it means point $0$ is inside the polygon; if $x = 0$, it means point $0$ is not inside the polygon.

After each output, do not forget to flush the buffer, for example: std::cout.flush()。

Input Format

See 【Implementation Details】.

Output Format

See 【Implementation Details】.

5 125

1

1

0

0

? 1 2 3

? 0 4 1

? 2 5 4

? 0 1 5

! 0

Hint

Sample Explanation

Constraints

For $100\%$ of the testdata, it is guaranteed that $3 \le N \le 500$.

Reminder again: the polygon is not necessarily convex. It is guaranteed that the polygon edges do not intersect. It is guaranteed that these $(N+1)$ points are pairwise distinct. It is guaranteed that no three points are collinear.

Special Property: $P$ is convex.

Translated by ChatGPT 5