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

这是一道交互题。

“大家快来！Doremy 的完美数据结构课马上就要开始啦！想和我一样聪明的话，就快来好好听课吧！”在今天的数据结构课上，Doremy 正在向大家讲解一种强大的数据结构——Doremy 树！现在，她给你出了一个测验，以证明你在认真听课。

给定一个长度为 $m$ 的数组 $a$，Doremy 树支持查询 $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$ 这些数中不同整数的个数。

Doremy 有一个由 $1$ 到 $n$ 的整数组成的秘密排列 $p$。你可以进行询问，在每次询问中，你给出 3 个整数 $l, r, k$（$1 \le l \le r \le n$，$1 \le k \le n$），并获得数组 $p$ 的 $Q(l, r, k)$ 值。你能在最多 25 次询问内，找到满足 $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)$ 值。在这个版本的题目中，你最多可以进行 25 次这样的询问。

要给出答案，你应当在单独的一行中输出：

• ! y（$1 \le y \le n$）

其中 $p_y = 1$。

在输出询问或答案后，请不要忘记输出换行符并刷新输出缓冲区（flush）。否则，你将获得 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$）——排列的长度。

第二行包含 $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 次询问后得到了正确答案，因此该过程将被判定为正确。