You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

绿茵不在，战场总在。

题目背景

在 SegonOJ 的绘板大战中，拜月教成功战胜拜日教，夺去了一半以上的资源！

值得一提，画面中的 CZOI、CFS、SCZ 标志等众多内容也是与拜月教的合作。

题目描述

拜日教教皇现在手上拥有众多 token，你作为拜月教的卧底，将要舌战交互库获得 token。

拜日教现在一共掌握 $n(1 \leq n \leq 10^9)$ 个 token。

拜日教教皇定义 $f(x)$ 表示 $x$ 在二进制下的 $1$ 的个数。

作为卧底来获取 token 的你，每次可使用 ? x$(0\leq x \leq 10^9)$ 查询 $f(n-x)$ 与 $f(k)$ 的关系；! n 输出一个答案，表示你猜测的拜日教教皇 token 数。如果错误，直接被拜日教教皇戳穿卧底身份，拜月教教皇会奖励你一个 WA。如果你说出的 token 数比拜日教教皇手中的还多，也会被戳穿并获得 WA。反之说出正确答案将会得到拜月教教皇信任，拜月教教皇会奖励你一个 AC。

我们设 $k=n$，拜日教教皇很狡猾，每次不会告诉你你的询问正确答案。如果拜日教教皇没骗你，查询时，若 $f(n-x)<f(k)$ 返回 $0$，$f(n-x)=f(k)$ 返回 $1$，$f(n-x)>f(k)$ 返回 $2$。若 $n-x<0$，那么直接忽略这个询问，表示认为你给出的 $x=0$。如果拜日教教皇骗你了，本该输出 $y$ 却会输出 $(y+1)\mod 3$。这个骗人序列周期长度为 $m$。同时，每次操作如果合法，$n\gets n-x$，表示将 $n$ 修改为 $n-x$。

为了不让拜日教教皇怀疑，你至多询问 $60$ 次。

输入格式

首先，拜月教皇会给出两个数字：$cnt$ 与 $m$，表示 $f(k)$ 与序列周期长度。

? x 查询 $f(n-x)$ 与 $f(k)$ 的大小。具体返回见题目描述。

你至多可以查询 $60$ 次。如果超过次数则也会被戳穿卧底身份。

交互特性

在输出之后，你需要使用以下语句：

你可以使用如下语句来清空缓冲区：

• 对于 C/C++：fflush(stdout)；
• 对于 C++：std::cout << std::flush；
• 对于 Java：System.out.flush()；
• 对于 Python：stdout.flush()；
• 对于 Pascal：flush(output)；
• 对于其他语言，请自行查阅对应语言的帮助文档。

特别的，对于 C++ 语言，在输出换行时如果你使用 std::endl 而不是 '\n'，也可以自动刷新缓冲区。

输出格式

! n 输出你的答案，这将作为你的最终结果，正确则成功套取拜日教 token，错误则被戳穿身份。

2 1

2

? 0

! 3

提示

特殊性质 $\tt A$：保证拜日教皇不会骗人。