AT_kupc2018_d.ロストテクノロジー

某天，通过对京都大学地下的调查，发现了一台使用了现已失传的古代超技术的竞赛编程装置。

如果向这台装置输入一个答案为正整数的竞赛编程题目和一个正整数 $q$，它会输出该题目的答案对 $q$ 取余的结果。

不过，由于这台装置的输出是用古文字书写的，你只能判断输出结果是偶数还是奇数。

你打算利用这台装置，来解答一个长期无人解出的竞赛编程题。该题的答案是满足 $1 \leq X \leq 10^9$ 的正整数 $X$。

但是，每使用一次这台装置都需要向京都大学支付巨额使用费，资金有限，因此装置的使用次数不得超过 $30$ 次。请你在 $30$ 次以内确定 $X$ 的值。

本题没有初始输入。

你的解答程序可以通过如下格式的输出来使用竞赛编程装置：

? $q$

其中 $q$ 是满足 $1 \leq q \leq 10^9$ 的正整数，表示输入给装置的参数。输出末尾需换行。

随后，你将收到一行字符串，表示装置的输出：

$r$

$r$ 为 even 或 odd。含义如下：

• even：表示 $X$ 对 $q$ 取余的结果是偶数。
• odd：表示 $X$ 对 $q$ 取余的结果是奇数。

装置的使用次数上限为 $30$ 次。如果超过 $30$ 次输出 ? q，将会收到 Query Limit Exceeded 的判定。

在多次使用装置后，你需要猜测题目的答案 $X$。如果你认为答案是 $answer$，则应输出：

! $answer$

输出末尾需换行。输出答案后，程序必须立即结束。若未结束，评测结果不确定。

此外，若输出格式不符合上述要求，评测结果也不确定。

请注意，每次输出后都需要刷新输出缓冲区。例如，在 C/C++ 中，使用装置时应如下输出：

printf("? %d\n", q); fflush(stdout);

无。

约束条件

• $1 \leq X \leq 10^9$
• $1 \leq q \leq 10^9$
• $X, q$ 均为整数
• 竞赛编程装置的使用次数不得超过 $30$ 次。

输入输出样例

以 $X = 3$ 为例，可能的输入输出如下：

解答程序的输出	装置的输出	说明
? $1$		向装置输入 $1$
	even	$X$ 对 $1$ 取余为 $0$，为偶数
? $2$		向装置输入 $2$
	odd	$X$ 对 $2$ 取余为 $1$，为奇数
? $5$		向装置输入 $5$
	odd	$X$ 对 $5$ 取余为 $3$，为奇数
! $3$		猜测 $X$ 为 $3$

这只是输入输出的一种示例，不保证有实际意义。

由 ChatGPT 4.1 翻译