“当格里高尔·萨姆莎（Gregor Samsa）一天早晨从不安的睡梦中醒来时，他发现自己躺在床上变成了一只巨大的甲虫”……这是卡夫卡小说《变形记》（Die Verwandlung）中著名的开篇名句。

鲜为人知的是，在从德语翻译的过程中，丢失了一个小小的技巧，即一个玩笑。谷歌翻译将上述句子（去掉最后一个词 verwandelt，意为“变形”）翻译为：“当格里高尔·萨姆莎一天早晨从不安的睡梦中醒来时，他发现自己的床上有一只巨大的甲虫。”这样，读者在第一句结尾处感到惊讶，并突然进入了当时一种新颖的荒诞小说类型。

不过，让我们把语言上的琐事放在一边。格里高尔现在是一只甲虫，位于平面上的点 $P_0$。他想知道自己是否位于 $N$ 边形 $P_1P_2 \dots P_N$ 的内部。

已知甲虫除了对 CCW（逆时针，counterclockwise）方向的直觉外，没有任何其他感知。因此，格里高尔可以询问任意三个点 $P_a, P_b, P_c$ 是否呈 CCW 顺序。

多边形 $P_1P_2 \dots P_N$ 不一定是凸的，但它不自交。点 $P_0, P_1, \dots, P_N$ 两两不同，且任意三点不共线。

定义：若点 $C$ 位于直线 $AB$ 的左侧（从点 $A$ 望向点 $B$），则称点 $A, B, C$ 呈 CCW 顺序。

左图中的点 $A, B, C$ 呈 CCW 顺序，而右图中的则不是。

交互

这是一个交互式题目。你的程序需要与组织者编写的程序进行对话。

在交互开始前，你的程序应从标准输入读取自然数 $N$（多边形的顶点数）和自然数 $Q$（你的程序允许发送的查询次数）。

之后，你的程序可以通过向标准输出写入内容来发送查询。每个查询应单独占一行，格式为 “? $a$ $b$ $c$”，其中 $0 \le a, b, c \le N$。每次输出查询后，你的程序必须刷新缓冲区，并从标准输入读取查询的回答——如果点 $P_a, P_b, P_c$ 呈 CCW 顺序，则回答为 $1$，否则为 $0$。特别地，如果索引 $a, b, c$ 不互不相同，回答将为 $0$。你的程序最多可以发送 $Q$ 次此类查询。

当你的程序得出结论后，应向标准输出写入 “!1”（如果点 $P_0$ 位于多边形内部）或 “!0”（如果点 $P_0$ 位于多边形外部）。随后，程序必须再次刷新缓冲区并结束运行。

说明：你可以通过评估系统下载示例源代码，这些代码展示了正确的交互方式，包括如何刷新输出。

子任务

样例

输入格式 1

5 125
1
1
0
0

输出格式 1

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