AT_arc078_c.[ARC078E] Awkward Response

这是一道交互题。

Snuke 有一个整数 $n \ (1 \le n \le 10^9)$，你可以用 ? x（$1 \le x \le 10^{18}$）向她提问。当 Snuke 收到提问时，她只有在满足下面两个条件之一的时候会回答 Y，其他时候都会回答 N。

• $x\le n$ 且 $\mathrm{str}(x)\le\mathrm{str}(n)$。
• $x\gt n$ 且 $\mathrm{str}(x)\gt\mathrm{str}(n)$。

这里 $\mathrm{str}(n)$ 表示 $n$（无前导 0）的十进制表示字符串，字符串的比较按字典序进行。$\mathrm{str}(111111111) \lt \mathrm{str}(9)$。

交互格式

当你需要提问时，输出一行 ? x，其中 $x$ 为一个 $1$ 到 $10^{18}$ 之间的整数，表示你询问的数字。在这之后，你需要读入一个表示答案的字符，只可能为 Y 或 N。

当你已经知道 Snuke 的数字时，输出一行 ! n，其中 $n$ 为你的答案。这不计入询问次数。

你需要在 $64$ 次询问之内得到答案。

null

null

• 每一次输出后需要换行并清空缓冲区，否则你可能得到 TLE。可以使用以下方法刷新输出：
  • C++：fflush(stdout) 或 cout.flush()；
  • Java：System.out.flush()；
  • Pascal：flush(output)；
  • Python：stdout.flush()；
  • 其他语言请参考相关文档。
• 输出答案之后，你应该立刻结束程序，否则交互库的行为未定义。
• 如果你的输出无效或者错误，交互库的行为未定义，它并不一定给出 WA 。

Translated by @Grammar_hbw。