E. 寻找 OR 和

时间与内存限制

• 时间限制：$2$ 秒
• 内存限制：$256$ MB

题目类型

交互题

题意翻译

有两个隐藏的非负整数 $x$ 和 $y$，满足 $0\le x,y<2^{30}$。 你可以进行不超过 $2$ 次以下形式的询问：

选择一个非负整数 $n$（$0\le n<2^{30}$），评测机会返回：

$$(n\mid x)+(n\mid y)$$

其中 $\mid$ 表示按位或运算。

询问结束后，评测机会给你另一个非负整数 $m$（$0\le m<2^{30}$）。 你必须正确回答出：

$$(m\mid x)+(m\mid y)$$

交互格式

每个测试点包含多组数据。 第一行一个整数 $t$（$1\le t\le 10^4$），表示测试用例组数。

每组数据内：

• 隐藏的 $x,y$ 是固定不变的，交互过程中不会改变。
• 每次询问：输出一个整数 $n$ 并换行，然后刷新缓冲区。
• 你会读到一个整数，表示 $(n\mid x)+(n\mid y)$ 的值。
• 最多只能询问 $2$ 次。

当你完成询问后：

• 输出一行 !。
• 然后你会读到一个整数 $m$。
• 你需要输出一行 $(m\mid x)+(m\mid y)$ 的正确结果。
• 这一行不算作询问。

之后进入下一组测试用例。

重要限制

• 询问次数不能超过 $2$，否则会直接判 Wrong Answer。
• 每次输出后必须刷新输出缓冲区，否则会被判 Idleness limit exceeded。

输入输出示例

输入（评测机返回）

2

3

4

1

0

1

输出（你的程序）

0

1

!

4

0

!

2

样例解释

第一组数据：

• 隐藏值 $x=1,y=2$。
• 询问 $n=0$，返回 $(0\mid 1)+(0\mid 2)=1+2=3$。
• 询问 $n=1$，返回 $(1\mid 1)+(1\mid 2)=1+3=4$。
• 输出 ! 后得到 $m=1$。
• 答案为 $(1\mid 1)+(1\mid 2)=4$。

第二组数据：

• 隐藏值 $x=0,y=0$。
• 询问 $n=0$，返回 $0+0=0$。
• 输出 ! 后得到 $m=1$。
• 答案为 $(1\mid 0)+(1\mid 0)=1+1=2$。