这是一个交互式问题。
Busy Beaver 有一个由 $1$ 到 $10^9$ 之间互不相同的正整数组成的秘密数组 $a_1, a_2, \dots, a_N$。对于 $1 \le l \le r \le N$，Busy Beaver 将 $f(l, r)$ 定义为 $\min(a_l, a_{l+1}, \dots, a_r)$。
Busy Beaver 允许你通过询问一些查询来获取有关该数组的信息。在一次查询中，你可以指定 $l$ 和 $r$（$1 \le l \le r \le N$），Busy Beaver 会告诉你 $f(l, r)$ 的值，代价为 $\frac{1}{r-l+1}$。你必须确保所有查询的总代价不超过 $1$。
在完成所有查询后，你需要向 Busy Beaver 报告一个二元组 $(l, r)$ 的列表，表示你已确定其 $f(l, r)$ 值的二元组。如果你的任何一个答案错误，Busy Beaver 将会不高兴并给你 $0$ 分。否则，你的得分将取决于在所有满足 $1 \le l \le r \le N$ 的 $\frac{N(N+1)}{2}$ 个二元组 $(l, r)$ 中，你确定了 $f(l, r)$ 值的二元组所占的比例（详见“子任务”部分）。
为了减少输出的大小，你需要使用 $k$ 个格式为 $(l_{\min}, l_{\max}, r_{\min}, r_{\max}, v)$ 的五元组来报告你所掌握的信息，其中 $1 \le l_{\min} \le l_{\max} \le r_{\min} \le r_{\max} \le N$ 且 $1 \le v \le 10^9$。每个五元组声明：对于所有满足 $l_{\min} \le l \le l_{\max}$ 且 $r_{\min} \le r \le r_{\max}$ 的 $(l, r)$，都有 $f(l, r) = v$。任何不对应任何五元组的二元组 $(l, r)$ 都将被视为未指定。允许有多个五元组描述同一个二元组 $(l, r)$，但如果这些五元组指示了不一致的值，你将获得 $0$ 分。
交互
输入的第一行包含一个整数 $N$（$1 \le N \le 10^5$），表示 Busy Beaver 秘密数组的长度。
你可以通过输出格式为 ? l r 的行来重复进行查询，其中 $1 \le l \le r \le N$。然后，评测机将响应一个整数，表示 $f(l, r)$ 的值。如果你超过了总代价 $1$，评测机将响应 -1，此时你应该立即终止程序以获得“答案错误（Wrong Answer）”的评测结果。
在结束查询后，首先输出一行格式为 ! k（$0 \le k \le 2N$），表示你将使用 $k$ 个五元组 $(l_{\min}, l_{\max}, r_{\min}, r_{\max}, v)$ 来描述你对 $f$ 的了解。
接下来的 $k$ 行，每行应包含 $5$ 个空格分隔的整数 $l_{\min}, l_{\max}, r_{\min}, r_{\max}$ 和 $v$，指定一个五元组。
交互器是非适应性的（non-adaptive），这意味着 Busy Beaver 不会根据你的查询来改变其秘密数组 $a$ 的元素。
子任务
对于所有用于评分的测试用例，$N = 10^5$。
如果你超过了代价 $1$，或者你声称的任何 $f(l, r)$ 值不正确，你将获得 $0$ 分并得到“答案错误（Wrong Answer）”的评测结果。
否则，设 $x$ 为你指定了值的 $f(l, r)$ 占全部 $\frac{N(N+1)}{2}$ 个值的比例。你在该测试用例上的得分将等于：
$$\left\lfloor \min\left(100, 100 \cdot \frac{x}{0.8}\right) \right\rfloor$$
特别地，如果 $x \ge 0.8$，你将获得该测试用例的满分。
你的最终得分将是所有测试用例中的最低得分。
样例
输入样例 1
6 31 26 53
输出样例 1
? 1 3 ? 1 6 ? 5 6 ! 4 1 1 3 3 31 1 4 4 6 26 2 3 5 5 26 5 5 6 6 53
说明
请注意，样例不满足 $N = 10^5$，因此它不会包含在实际的测试用例中。它仅用于说明交互格式。
在样例中，Busy Beaver 的秘密数组为 $a = [31, 41, 59, 26, 53, 58]$。你决定进行以下查询：
- $l = 1, r = 3$：Busy Beaver 计算 $f(1, 3) = \min(31, 41, 59) = 31$ 并告诉你值 $31$。
- $l = 1, r = 6$：Busy Beaver 计算 $f(1, 6) = \min(31, 41, 59, 26, 53, 58) = 26$ 并告诉你值 $26$。
- $l = 5, r = 6$：Busy Beaver 计算 $f(5, 6) = \min(53, 58) = 53$ 并告诉你值 $53$。
注意，你所有查询的总代价为 $\frac{1}{3} + \frac{1}{6} + \frac{1}{2} = 1$，没有超过要求的限制 $1$。
根据这些信息，你向 Busy Beaver 报告了你推导出的以下 $f(l, r)$ 值：
- 对于所有 $1 \le l \le 1, 3 \le r \le 3$，有 $f(l, r) = 31$。
- 对于所有 $1 \le l \le 4, 4 \le r \le 6$，有 $f(l, r) = 26$。
- 对于所有 $2 \le l \le 3, 5 \le r \le 5$，有 $f(l, r) = 26$。这与前一行的信息有重叠，但这是一个有效的输出。
- 对于所有 $5 \le l \le 5, 6 \le r \le 6$，有 $f(l, r) = 53$。
在去除重叠后，你在 $\frac{N(N+1)}{2} = 21$ 个不同的二元组 $(l, r)$ 中，报告了其中的 $14$ 个 $f(l, r)$ 值。因此，Busy Beaver 将计算出 $x = \frac{14}{21}$，并在此次交互中给予你以下分数：
$$\left\lfloor 100 \cdot \frac{14/21}{0.8} \right\rfloor = \lfloor 83.\bar{3} \rfloor = 83$$