本题与另外两个版本的唯一区别在于最大询问次数。在这个版本中，你最多允许进行 $30$ 次询问。只有当本题的所有版本都被解决时，你才能进行 Hack。

这是一个交互式问题。

“大家请注意！哆来咪的完美数据结构课马上就要开始了！如果你想拥有和我一样高的 IQ，就快来大显身手吧！”在今天的数据结构课上，哆来咪正在向大家介绍一种强大的数据结构——哆来咪树（Doremy tree）！现在，她给你出了一个测验，以证明你在认真听课。

给定一个长度为 $m$ 的数组 $a$，哆来咪树支持查询 $Q(l, r, k)$，其中 $1 \le l \le r \le m$ 且 $1 \le k \le m$，该查询返回数组 $\lfloor \frac{a_l}{k} \rfloor, \lfloor \frac{a_{l+1}}{k} \rfloor, \dots, \lfloor \frac{a_r}{k} \rfloor$ 中不同整数的个数。

哆来咪有一个由 $1$ 到 $n$ 的整数组成的隐藏排列 $p$。你可以进行询问，在一次询问中，你给出 $3$ 个整数 $l, r, k$ ($1 \le l \le r \le n, 1 \le k \le n$)，并接收数组 $p$ 的 $Q(l, r, k)$ 值。你能在最多 $30$ 次询问内找到满足 $p_y = 1$ 的下标 $y$ ($1 \le y \le n$) 吗？

请注意，排列 $p$ 在进行任何询问之前就已经确定。

交互

你需要首先从第一行读取一个整数 $n$ ($3 \le n \le 1024$)——排列的长度，以此开始交互。

为了进行询问，你应该在单独的一行中输出：

• ? l r k ($1 \le l \le r \le n, 1 \le k \le n$)

在每次询问后，你应该读取一个整数 $x$——排列 $p$ 的 $Q(l, r, k)$ 值。在这个版本的题目中，你最多可以进行 $30$ 次这样的询问。

为了给出答案，你应该在单独的一行中输出：

• ! y ($1 \le y \le n$)

其中 $p_y = 1$。

在输出询问或答案后，请不要忘记输出换行符并刷新输出缓冲区。否则，你将获得 Idleness limit exceeded（超出空闲限制）。为此，请使用：

• C++ 中的 fflush(stdout) 或 cout.flush()；
• Java 中的 System.out.flush()；
• Pascal 中的 flush(output)；
• Python 中的 stdout.flush()；
• 其他语言请参阅相关文档。

Hack 格式

Hack 数据的首行包含一个整数 $n$ ($3 \le n \le 1024$)——排列的长度。

Hack 数据的第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$)——该排列。

样例

输入样例 1

5

2

2

1

3

输出样例 1

? 1 3 4

? 3 5 3

? 3 4 5

? 3 5 2

! 4

说明

样例中的排列为 $[3, 5, 2, 1, 4]$。

样例中的输入和输出展示了在该测试点上可能的一种交互过程（插入空行仅为了清晰起见）。

在此交互过程中：

• 对于第一次询问，$\lfloor \frac{3}{4} \rfloor = 0, \lfloor \frac{5}{4} \rfloor = 1, \lfloor \frac{2}{4} \rfloor = 0$，因此答案为 $2$。
• 对于第二次询问，$\lfloor \frac{2}{3} \rfloor = 0, \lfloor \frac{1}{3} \rfloor = 0, \lfloor \frac{4}{3} \rfloor = 1$，因此答案仍为 $2$。
• 对于第三次询问，$\lfloor \frac{2}{5} \rfloor = 0, \lfloor \frac{1}{5} \rfloor = 0$，因此答案为 $1$。
• 对于第四次询问，$\lfloor \frac{2}{2} \rfloor = 1, \lfloor \frac{1}{2} \rfloor = 0, \lfloor \frac{4}{2} \rfloor = 2$，因此答案为 $3$。

在 $4$ 次询问后得到了正确答案，因此该过程将被判定为正确。