出于安全考虑，TU Delft 准备在大量房间的门上安装带有数字键盘的锁。每个房间都将拥有自己的密码。设置存储所有密码的服务器的任务交给了 Harry 和 Sharon。

在参加了网络安全课程后，他们知道密码在存储之前应该通过哈希函数进行处理，最好是多次处理。

Sharon 提出了一个巧妙的想法：让房间号作为密码通过哈希函数的次数。这样，即使两个房间恰好有相同的密码，它们也不一定会得到相同的哈希值。然而，他们发现对于某些房间号和密码的组合，哈希值恰好与原始密码相同，这构成了安全风险。

Harry 不甘示弱，提出了自己的想法：交换角色，即让密码作为哈希函数应用于房间号的次数。换句话说，如果 $c$ 是密码，$r$ 是房间号，那么哈希值将是 $f^c(r) = \underbrace{f(\dots f(}_{c \text{ 次}}r)\dots)$。

经过一番思考，Sharon 声称，无论函数 $f$ 是什么，对于某些房间号和密码，哈希值总是会与密码相同；也就是说，$f^c(r) = c$。事实上，Sharon 认为即使不知道 $f$ 的全部细节，找到这样两个数字也不太困难。

这种轻蔑的言论让 Harry 很生气，他认为 Sharon 只是嫉妒他的想法。在一番毫无结果的争论后，Harry 决定让 Sharon 证明她的主张：他编写了一个程序，在发送查询时，会返回查询中给定的 $c$ 和 $r$ 的哈希值 $f^c(r)$，并使用他选择的秘密哈希函数 $f$。该哈希函数接受 $\{1, \dots, n\}$ 中的任何 $r$（其中 $n$ 是给定的），并返回相同范围内的值。$c$ 的值也应在该范围内。Sharon 的挑战是找到 $c$ 和 $r$ 使得 $f^c(r) = c$，且查询次数有限。

你知道 Sharon 的主张是正确的，并决定帮助她。

在第一个样例中，$n$ 的值为 $6$，隐藏函数为 $f(1) = 4, f(2) = 3, f(3) = 5, f(4) = 2, f(5) = 4, f(6) = 6$。在第二个样例中，$n = 4$，且 $f(1) = 2, f(2) = 4, f(3) = 2, f(4) = 2$。

交互

这是一个交互式问题。你的提交将针对一个交互器运行，该交互器读取你的提交的输出并写入你的提交的输入。此交互需要遵循特定的协议：

交互器首先发送一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)，表示隐藏函数 $f$ 的定义域为 $\{1, \dots, n\}$。

然后，你的程序应进行最多 $1000$ 次查询以找到答案。每次查询通过打印一行格式为 “? c r” ($1 \le c, r \le n$) 的内容来完成。交互器将返回一个整数 $h$ ($1 \le h \le n$)，即 $f^c(r)$ 的值。

当你确定了某些满足 $f^c(r) = c$ 的 $c$ 和 $r$ 值时，打印一行格式为 “! c r” ($1 \le c, r \le n$) 的内容，之后交互将停止。打印答案不计入查询次数。

如果有多个有效的解决方案，你可以输出其中任何一个。

交互器不是自适应的：隐藏函数 $f$ 是预先固定的，不依赖于你的查询。

确保在每次写入后刷新缓冲区。

提供了一个测试工具来帮助你开发解决方案。

使用超过 $1000$ 次查询将导致错误答案。

样例

样例交互 1

6
? 2 4
3
? 4 1
5
? 5 5
4
? 1 6
6
? 2 1
2
! 2 1

样例交互 2

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