黑洞

本题为交互题。

科学家计划测量一系列黑洞的辐射等级。一个黑洞的辐射等级是一个从 $1$ 到 $n$ 的整数。对于每个黑洞，科学家都会派出一个专用的轨道探测器，探测器上装有辐射传感器。

传感器可以回答如下形式的问题：给定一个整数 $x$，判断该黑洞的辐射等级是否大于等于 $x$。

不幸的是，由于软件错误，传感器的回答可能有一次是错误的。幸运的是，一旦它第一次给出了错误回答，从那以后这个传感器会改变状态，后续所有回答都一定正确。

科学家希望对若干个黑洞分别确定其辐射等级，并且对每个黑洞询问传感器的次数不能太多。

你需要编写一个程序，与评测程序交互，模拟询问探测器，并确定每个黑洞的辐射等级。

对于同一次程序运行，需要处理若干个黑洞，它们的 $n$ 相同。黑洞数量不告知选手程序；程序应一直处理，直到评测程序返回 Done。

对于每个测试点，评测程序固定了一个数 $q$，表示每个黑洞最多允许询问的次数。保证存在一种策略，可以在不超过 $q$ 次询问内确定答案。这个 $q$ 不会告诉选手程序。如果你的程序对某个黑洞询问超过 $q$ 次，则该测试点判为 Wrong Answer。

交互格式

程序开始时，评测程序会向你的程序输入一个整数 $n$，表示辐射等级的最大可能值：

$$1 \le n \le 30000$$

这个 $n$ 对本次运行中所有黑洞都相同。

随后，你的程序需要依次确定一个或多个黑洞的辐射等级。

询问

若要询问传感器，请输出一行：

? x

其中 $x$ 是整数，且 $1 \le x \le n$。

评测程序会返回一行：

• Yes：传感器声称黑洞辐射等级大于等于 $x$；
• No：传感器声称黑洞辐射等级小于 $x$。

注意：同一个黑洞的所有回答中，最多有一次可能是错误回答；并且一旦出现第一次错误回答，之后的回答都是真实的。

回答

如果你已经确定当前黑洞的辐射等级，请输出一行：

! x

其中 $x$ 是你确定的辐射等级。

如果 $x$ 是唯一一个与当前黑洞已收到的所有回答中至多一个回答矛盾的等级，则答案被认为正确。

输出答案后，你的程序需要读入评测程序返回的一行：

• Correct：当前黑洞回答正确，接下来需要继续处理下一个黑洞；
• Done：所有需要处理的黑洞都已完成，你的程序应立即结束。

如果答案错误，评测程序会终止交互，并给出 Wrong Answer。

评测程序可能会根据你的询问自适应地决定回答方式。保证在每次回答后，至少存在一个辐射等级，使得此前对当前黑洞的回答中至多有一个是错误的。

重要提示

每次输出询问或答案后，必须刷新输出缓冲区。例如：

• C++：可以使用 cout << endl;，或输出 \n 后调用 fflush(stdout) / cout.flush()；
• Java：可以调用 System.out.flush()；
• Python：可以使用 print(..., flush=True)。

样例交互 1

下面左侧表示评测程序输入给选手程序的内容，右侧表示选手程序输出的内容。

交互器输入：

2

Yes

No

Yes

Correct

No

No

Done

选手程序输出：

? 2

? 2

? 2

! 2

? 2

? 2

! 1

样例交互 2

交互器输入：

3

Yes

Yes

No

Yes

No

Done

选手程序输出：

? 2

? 2

? 3

? 3

? 3

! 2

样例说明

在第一个样例中，对于第一个黑洞，前两次询问后还无法确定究竟哪一次回答可能是错误的，因此还需要第三次询问。

第二个样例展示了 $n=3$ 时的一种可能交互过程，它用 5 次询问确定答案。可以证明，用 4 次询问无法保证确定答案。

两个样例中，评测程序使用的限制均为 $q=30$。

请注意：即使你的程序发出与样例完全相同的询问，评测程序也可能给出不同的合法回答。

子任务与评分

在子任务 3 到 17 中，每个测试点的 $q$ 都等于在对应 $n$ 下能够保证确定答案所需的最少询问次数。

子任务	分值	限制	询问限制
1	7	$n \le 1000$	$q=30$
2	8		$q=21$
3	6	$n \le 4$	$q$ 为最优值
4	9	$n \le 7$
5		$n \le 12$
6		$n \le 25$
7	4	$n \le 40$
8	5	$n \le 80$
9		$n \le 150$
10	8	$n \le 300$
11	7	$n \le 500$
12	5	$n \le 1000$
13		$n \le 2000$
14		$n \le 4000$
15		$n \le 8000$
16		$n \le 15000$
17		$n \le 30000$