题目描述

译自 ROI 2019 Day1 T4. Чёрная дыра

这是一道交互题。

科学家们想要测量一些黑洞的辐射大小，辐射大小用一个 $\ge 1$ 且 $\le n$ 的整数来表示。在轨道上有可以测量辐射大小的传感器。

每次探测时，你给传感器输入一个数 $x$，传感器可以应答辐射水平是否 $\ge x$。但是，每个传感器可能会给出不正确的答案。幸好，在传感器给出了一次错误答案之后，它之后给出的所有答案都是正确的。

科学家们希望通过对探测每个黑洞的探测器提出不太多的询问，求出这几个黑洞的辐射水平。

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

一组测试点中黑洞的 $n$ 值是一样的。一次运行中的黑洞数量不超过 $100$ 个，你的程序不会知道这个值。

每组测试数据都有一个固定数字 $q$，这是一个黑洞所允许的最大查询数。可以保证的是，无论交互器给出什么回答，都可以在 $q$ 次查询之内解决问题。你的程序也不会知道这个数字。表中给出了不同子任务中 $q$ 的限制，并附有评分系统的信息。如果你的程序在对一个黑洞的判定中进行了超过 $q$ 次的查询，它就会被判为答案错误。

交互过程

首先你的程序应该从标准输入中读入一个整数 $n\ (1\le n\le 3\cdot 10^4)$，表示黑洞最大的辐射水平。在这组测试点中所有黑洞的最大可能辐射水平都是 $n$。在读入 $n$ 之后，你的程序需要与交互器交互并连续地确定一个或多个黑洞的辐射水平。

程序应该对传感器进行询问，并获得关于辐射水平的答案。

对于询问，程序应该向标准输出输出一个字符串 $\texttt{? }x$，其中 $x$ 是一个正整数（$1\le x\le n$）。如果传感器报告这个黑洞的辐射水平大于或等于 $x$，则交互器会向标准输入写入字符串 $\texttt{Yes}$，如果报告这个黑洞的辐射水平小于 $x$，则写入 $\texttt{No}$。

如果程序已经确定了这个黑洞的辐射水平，程序应该向标准输出输出一个字符串 $\texttt{! }x$，其中 $x$ 是这个黑洞的辐射水平。如果 $x$ 只和不超过 $1$ 个传感器对这个黑洞辐射水平的回答相悖的话，那么这个答案就被认为是正确的。

在输出这个黑洞的答案后，你的程序仍然要读入一行，如果还有必要继续处理下一个黑洞的话，交互器会向标准输入写入字符串 $\texttt{Correct}$。如果没有黑洞要继续处理的话，交互器会向标准输入中写入字符串 $\texttt{Done}$，你的程序应当停止。

如果你的程序给出了错误的答案，你的程序会被强行终止，并判为答案错误。

可以保证，在交互器做出每个回答之后，都存在这样的辐射水平，即除了最多一个黑洞之外，所有先前对该黑洞询问的答案都是正确的。交互器可以调整其行为，包括选择哪个已经给出的答案是错误的，以及被调查黑洞的辐射水平是什么，这取决于程序的查询，也就是说交互器是自适应性的。

样例交互

第一个交互过程

在这个例子中，对于询问两次后的第一个黑洞，是不能确定哪次回答是错误的，所以需要第三次询问。

第二个交互过程

第二个例子给出了一种 $n=3$ 的可能交互，在五次询问之后得到了答案。可以证明不可能用四次询问找到答案。

这两个测试点中，都有 $q=30$。

请注意，尽管程序可能提出与样例中完全相同的询问，交互器也可能会给出不同的答案。

数据范围及限制

在子任务 $3\sim 17$ 的每组测试数据中，$q$ 的值等于可以保证知道黑洞发射水平次查询中最小的查询数量，这个值独立于测试点中的 $n$ 值和传感器响应。