2854 「CEOI2012」公路设计

译自 CEOI 2012 Day2 T1「Highway Design」

政府决定修建一条穿越 $N$ 个城市的高速公路系统。每个城市都已经指定了其路口的理想位置。政府规定高速公路只能沿直线修建。奇迹般地，两条高速公路竟然足以到达所有的城市，也就是说，可以定义两条线，这样每个交点都在一条线上。此外，这两条线都包含至少三个交点，并且在这两条线的交点处没有交点。很容易证明，在这些条件下，线是唯一确定的。你的公司的工作是建立这个高速公路系统，因此你想知道这两条代表高速公路的直线的轨迹。路口的坐标已经在土地办公室登记，但你只被允许向办公室提交查询，询问某些给定的三个路口是否共线。由于查询需要大量的处理费用（您知道这些官僚……），所以您的目标是尽可能少地询问查询。

因为两个连接点完全决定了一条直线的轨迹，你的任务是确定两条直线的每个连接点。

您将编写一个程序，以尽可能少的查询来确定两条高速公路上的两个路口。

本题需使用 I/O 交互。

在程序的开始，请从标准输入中读入一个正整数 $N$，表示城市的个数。路口从 $1$ 到 $N$ 编号。

接下来开始交互，按如下格式输出到标准输出以完成交互过程：

• ? x y z：其中 $x,y,z$ 为路口编号。如果路口 $x,y,z$ 共线，则交互器返回整数 $1$，否则返回 $0$。注意两个点一定是共线的。
• ! a1 b1 a2 b2：表示最终的回答，其中 $\texttt{a1, b1}$ 是在一条线上的两个路口，$\texttt{a2, b2}$ 是在另一条线上的两个路口。在输出这条回答后，交互器不返回任何信息，你应该终止程序。

对于每个操作都必须输出一个换行符，并且刷新标准输出缓冲区。

对于所有数据，都有 $20\le N\le 10^5$。

评分器不使用预先确定的输入，它会回答查询而不自相矛盾。你的程序只有在被你的程序之前进行的查询所暗示的情况下才会被判为正确。(猜测是没有意义的。）

本题有 $25$ 组测试数据。对于每组数据，如果你的程序是正确的，并且询问了 $K$ 次，那么：

• 如果 $K\le \frac{N}{2}+2$，则获得 $4$ 分；
• 如果 $K\le \frac{2N}{3}$，则获得 $2$ 分；
• 如果 $K\le N-3$，则获得 $1$ 分；
• 否则获得 $0$ 分。

你可以假设评分器回答查询的方式是，如果不进行至少 $\frac{N}{3}$ 次查询，你的程序将无法提供一个正确的答案。