人们是如何构思题目的呢？有时他们只是把几个流行词汇拼凑在一起。但现在是 2024 年，这完全可以外包给 AI。隆重介绍我们基于 ChatGPT 的创作：RICH B！这是它的第二个正式题目：

提示：最小生成树

题目：给定一个包含 $n$ 个节点和 $\frac{n(n-1)}{2}$ 条边的完全图。每条边都被随机赋予一个 $[0, 1]$ 范围内的实数权重。你的任务是找到它的最小生成树。但你并不知道这些边的权重。相反，你可以进行形如 “? $v_1$ $u_1$ $v_2$ $u_2$” 的查询，评测程序将返回 1 表示边 $(v_1, u_1)$ 的权重小于边 $(v_2, u_2)$ 的权重，否则返回 0。

当你认为你已经找到了最小生成树时，请按 “! $v_1$ $u_1$ $v_2$ $u_2$ ... $v_{n-1}$ $u_{n-1}$” 的格式输出，其中边 $(v_i, u_i)$ 构成了最小生成树。数据范围：$2 \le n \le 100$，且你最多可以进行 6000 次查询。

交互

首先，读取一行包含单个整数 $n$ ($2 \le n \le 100$) 的内容：图的大小。

要比较两条边，请按以下格式打印一行：“? $v_1$ $u_1$ $v_2$ $u_2$”。然后你需要读取一行比较结果：如果第一条边的权重小于第二条边的权重，则返回 1，否则返回 0。

要输出答案，请按以下格式打印一行：“! $v_1$ $u_1$ $v_2$ $u_2$ ... $v_{n-1}$ $u_{n-1}$”。你的程序在打印此行后必须立即终止，否则可能会得到不可预知的判决。

在你打印的每一行中，$(v_i, u_i)$ 应当是满足 $1 \le v < u \le n$ 的整数对，否则你可能会得到不可预知的判决。

你的程序进行的比较次数不得超过 6000 次。

样例

输入 1

3
1
1

输出 1

? 1 2 1 3
? 1 3 2 3
! 1 2 1 3

说明

图的最小生成树（MST）定义为该图所有生成树中总权重最小的那棵树。

生成树是给定图的一个连通子图，它包含图中所有的顶点且不包含环。

交互器是非自适应的。

请记住在打印每一行后换行并刷新输出。在 C/C++ 中，可以使用 fflush(stdout)；在 Java 中，可以使用 System.out.flush()；在 Python 中，可以使用 sys.stdout.flush() 来刷新输出。