题目背景

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

众所周知，昆虫只对顺逆时针方向有感觉。

由于没有 std，不保证 SPJ 正确性。如果怀疑 SPJ 有误，请联系搬题人。SPJ 代码。

题目描述

这是一道交互题。

二维平面上有一个 $N$ 个点的多边形 $P$。注意 $P$ 不一定是凸的（它可以是凹包）。我们将多边形上的点依次编号为 $1\sim N$。

此外，还有一个额外的点 $0$。试通过交互来确定它是否在 $P$ 内部。

保证多边形的线段不交。保证这 $(N+1)$ 个点两两不同。保证无三点共线。

定义：$A,B,C$ 逆时针排列当且仅当从 $A$ 看向 $B$ 时，$C$ 在直线 $AB$ 左侧。如左图。

【实现细节】

交互开始前，需要读入一行两个整数 $N,Q$，表示多边形点数，和允许的最大询问数。

接下来，你的程序通过标准输入输出流与交互库交互。以下是允许的询问：

• $\texttt{? a b c}$：询问点 $a,b,c$ 是否逆时针排列。必须保证 $a,b,c$ 两两不同，且 $0\le a,b,c\le N$。

  如果 $a,b,c$ 逆时针排列，回答为 $1$；否则回答为 $0$。

确定答案后，按照以下格式回答：

• $\texttt{! x}$：如果 $x=1$，则代表 $0$ 号点在多边形内部；$x=0$ 代表 $0$ 号点不在多边形内部。

每次输出后，别忘了刷新缓冲区。如：std::cout.flush()。

输入格式

见【实现细节】。

输出格式

见【实现细节】。

5 125

1

1

0

0

? 1 2 3

? 0 4 1

? 2 5 4

? 0 1 5

! 0

提示

样例解释

数据范围

对于 $100\%$ 的数据，保证 $3\le N\le 500$。

再次提醒，多边形不一定是凸的。保证多边形的线段不交。保证这 $(N+1)$ 个点两两不同。保证无三点共线。

子任务编号	$N\le$	$Q=$	特殊性质	得分
$1$	$50$	$N^3$	有	$5$
$2$			无	$25$
$3$	$500$	$N^2$		$15$
$4$		$4N$		$25$
$5$		$2N$		$30$

特殊性质：$P$ 是凸的。