题目背景

翻译自 ROI 2019 D1T4。

这是一道 IO 交互题。

科学家计划测量一系列黑洞的辐射等级。黑洞的辐射等级由一个从 $1$ 到 $n$ 的整数表示。为了测量每个黑洞的辐射等级，使用一个特殊的轨道探测器，上面安装有辐射传感器。安装在探测器上的传感器可以回答以下查询：根据给定的 $x$ 值，确定辐射等级是否大于或等于 $x$。不幸的是，由于软件错误，传感器的回复可能是错误的。不过，在第一个错误回复之后，该探测器的状态就会改变，对所有后续的查询只给出正确的回复。

科学家想要通过向其导向的探测器提出尽可能少的查询来确定几个黑洞的辐射等级。

题目描述

编写一个程序与模拟探测器传感器的交互库进行交互，并确定每个黑洞的辐射等级。

对于每次运行的解决方案程序，必须解决 $n$ 相同的多个黑洞的问题（即，需要确认多个黑洞的辐射等级，这些黑洞的辐射等级都在 $1$ 和 $n$ 之间）。每次的黑洞数量不超过 $100$。

对于每个测试点，交互库记录了 $q$ 的值，也就是允许对一个黑洞进行的最大查询次数。保证无论选择的交互程序如何回答，$q$ 个查询足以解决问题。此数字不会被告知给你的程序。如果你的程序对一个黑洞进行了超过 $q$ 个查询，则这个测试点将会返回 WA。

注：在上述 WA 的情况下，该测试点可能显示为 TLE，有可能是因为交互库已经结束并返回，但程序仍在等待该查询的回复。TLE 时可以查看该测试点返回的详细信息，以确认是程序超时还是询问次数超出限制导致的。

输入格式

首先输入一个数 $n$，也就是黑洞的最大辐射强度。这个数字对于本次运行中的所有黑洞是相同的。读取 $n$ 后，你的程序应与交互库进行交互并逐步确定一个或多个黑洞的辐射等级。

在输出完你对一个黑洞辐射等级的回答后，程序应另外读取一行。如果需要继续对下一个黑洞进行研究，则从交互库读入的字符串为 Correct；如果所有的黑洞都已经研究完成，则字符串应该为 Done。

输出格式

要进行查询，程序必须输出格式为 ? x 的字符串，其中 $x$ 是一个正整数。作为回答，交互库将给你的程序一个字符串，要么是 Yes（如果传感器的回复没有出错，就代表该黑洞的辐射等级大于或等于查询中指定的 $x$ 值），要么是 No（如果传感器的回复没有出错，就代表该黑洞的辐射等级小于查询中指定的 $x$ 值）。

如果你的程序确定了问题的答案，则它应该输出一行 ! x，其中 $x$ 是要查找的黑洞的辐射等级。如果 $x$ 是唯一那个与不多于一个交互库的回复相冲突的辐射水平值，则该答案被视为正确的。如果给出了错误答案，程序将被强制终止，并且该测试点的结果将会变为 WA。

2

Yes

No

Yes

Correct

No

No

Done

? 2

? 2

? 2

! 2

? 2

? 2

! 1

3

Yes

Yes

No

Yes

No

Done

? 2

? 2

? 3

? 3

? 3

! 2

提示

样例解释：

在第一个示例中，对于第一个黑洞，在前两次查询之后不知道传感器的答案错误在哪一个上面，因此需要进行第三个查询。

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

在这两个样例中，交互库确定的 $q=30$，明显的，这两个样例都没有超出界限。

请注意，交互库可能给出不同的答案，即使程序输出与样例中完全相同的查询。

数据范围：

子任务	分值	$n\le$	$q$ 的特殊性质
$1$	$7$	$1000$	$q=30$
$2$	$8$		$q=21$
$3$	$6$	$4$
$4$	$9$	$7$
$5$		$12$
$6$		$25$
$7$	$4$	$40$
$8$	$5$	$80$
$9$		$150$
$10$	$8$	$300$
$11$	$7$	$500$
$12$	$5$	$1000$
$13$		$2000$
$14$		$4000$
$15$		$8000$
$16$		$15000$
$17$		$30000$

对于 $100\%$ 的数据，$n\le30000$。每个测试中的 $q$ 值都保证无论选择的交互程序如何回答，$q$ 个查询足以解决问题。

保证在交互库给出的每个答案之后，都一定存在一个辐射水平值，满足所有先前查询的答案（除了那次错误的）。交互库可以调整自己的行为，包括选择哪个已知答案是错误的，以及根据解决方案程序提出的查询来确定正在研究的黑洞的辐射水平。