这是一个交互式问题。

科学家们计划测量一系列黑洞的辐射水平。黑洞的辐射水平由一个 $1$ 到 $n$ 之间的整数表示。为了测量每个黑洞的辐射水平，我们使用专门的轨道探测器，上面安装了辐射传感器。

安装在探测器上的传感器可以回答以下查询：给定值 $x$，判断辐射水平是否大于或等于 $x$。遗憾的是，由于软件错误，传感器的回答可能是错误的。幸运的是，在第一次错误回答之后，该探测器的传感器会改变其状态，并在随后的所有查询中只给出正确的回答。

科学家们希望通过对每个黑洞的探测器进行不超过一定次数的查询，来确定其辐射水平。

你需要编写一个程序，与模拟探测器传感器的评测程序进行交互，并确定每个黑洞的辐射水平。

对于每次运行，你需要解决多个具有相同 $n$ 值的黑洞的辐射水平问题。单次运行中黑洞的数量不超过 $100$，且不会告知你的程序。

对于每个测试点，评测程序固定了一个值 $q$ —— 允许对单个黑洞进行的最大查询次数。保证 $q$ 次查询足以在无论评测程序给出何种回答的情况下解决问题。该值不会告知你的程序。如果你的程序对单个黑洞进行的查询次数超过了 $q$，则该测试点将被判为“答案错误”。

交互协议

首先，输入一个整数 $n$ —— 黑洞辐射水平的最大可能值 ($1 \le n \le 30\,000$)。该值对于本次运行中所有待测黑洞均相同。读取 $n$ 后，你的程序必须与评测程序进行交互，以依次确定一个或多个黑洞的辐射水平。

程序必须执行对传感器的查询并获取关于辐射水平的回答。

要进行查询，你的程序必须输出一行格式为 ? x 的字符串，其中 $x$ 是一个正整数 ($1 \le x \le n$)。

作为对查询的响应，评测程序会输入一行字符串：如果传感器报告黑洞的辐射水平大于或等于查询中给定的 $x$，则输入 Yes；如果传感器报告黑洞的辐射水平小于 $x$，则输入 No。

如果你的程序确定了问题的答案，则必须输出一行 ! x，其中 $x$ 是所求的黑洞辐射水平。如果 $x$ 是唯一一个与该黑洞收到的所有评测程序回答矛盾不超过一次的辐射水平，则该黑洞的答案被视为正确。

在输出当前黑洞的答案后，程序必须读取一行字符串。如果需要开始研究下一个黑洞，输入将是 Correct。

如果所有需要的黑洞都已研究完毕，输入将是 Done。在这种情况下，你的程序必须终止运行。

如果对某个黑洞给出了错误的答案，你的程序将被强制终止，并在该测试点获得“答案错误”的结果。

保证在评测程序的每次回答之后，都存在一个辐射水平值，使得该黑洞之前所有的查询回答中，至多有一个是错误的。评测程序可能会根据你的程序所做的查询来调整其行为，包括选择之前给出的哪一个回答是错误的，以及确定当前黑洞的辐射水平。

样例

输入格式 1

2
Yes
No
Yes
Correct
No
No
Done

输出格式 1

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

说明

在第一个样例中，对于第一个黑洞，在前两次查询后，无法确定哪一次传感器的回答是错误的，因此需要第三次查询。

输入格式 2

3
Yes
Yes
No
Yes
No
Done

输出格式 2

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

说明

在第二个样例中，展示了 $n=3$ 时的一种可能的交互过程，该过程在 $5$ 次查询内找到了答案。可以证明，在 $4$ 次查询内无法确定答案。

在两个样例中，解法均在 $q=30$ 的条件下进行测试。请注意，即使你的程序在样例中进行了完全相同的查询，评测程序也可能给出不同的回答。