Mirko 今天向 Slavko 隐藏了一棵包含 $N$ 个节点的树。Slavko 非常想知道 Mirko 的树长什么样，但他唯一知道的是树中每个节点的度数最多为 3，即每个节点最多有三个邻居。

Mirko 同情 Slavko，允许他向树提出 $K$ 个问题。对于给定的三个不同节点 $a, b$ 和 $c$，Mirko 将回答：

• $0$：如果节点 $a$ 到 $b$ 的距离等于节点 $a$ 到 $c$ 的距离。
• $1$：如果节点 $a$ 到 $b$ 的距离小于节点 $a$ 到 $c$ 的距离。
• $2$：如果节点 $a$ 到 $b$ 的距离大于节点 $a$ 到 $c$ 的距离。

节点 $u$ 和 $v$ 之间的距离定义为它们路径上的边数。

请帮助 Slavko 确定 Mirko 的树！

交互

这是一个交互式题目。你的程序需要与主办方编写的程序进行对话。

首先，你的程序需要从标准输入读取整数 $N$，即树的大小。

然后，可以通过向标准输出打印来发送查询。每个查询必须打印在单独的一行中，格式为 “? a b c”，其中 $a, b, c$ 是满足 $1 \le a, b, c \le N$ 且 $a \neq b, b \neq c, c \neq a$ 的自然数。数字 $a, b, c$ 代表 Slavko 想要询问的树节点。你的程序最多可以提出 $250\,000$ 个此类查询。

在打印每个查询后，程序必须刷新输出，并从标准输入读取对查询的回答——一个非负整数 $k$，其中 $k \in \{0, 1, 2\}$。

当完成所有查询后，程序应打印字符 “!” 以标记 Slavko 提问的结束，并刷新输出。

之后，需要打印 Mirko 树的边。即打印 $N-1$ 行，其中第 $i$ 行包含一对数字 $u_i$ 和 $v_i$，代表 Mirko 树中的一条边。边中节点的顺序以及边的打印顺序均不重要。必须打印所有边。

打印完答案后，你的程序应刷新输出并终止运行。

子任务

在所有子任务中，$N < 512$。

假设你的程序在某个子任务中使用了最多 $K$ 次查询来获得解。该子任务的得分将为：

$$\min \left( 1, \left( \frac{14000}{K} \right)^{0.7} \right) \cdot B$$

其中 $B$ 是该子任务的分值。仅计算格式为 “? a b c” 的查询。

样例

假设 Mirko 的树包含边 $(1, 2), (2, 3)$ 和 $(3, 4)$。