题目重述

有两个隐藏的非负整数 $x$ 和 $y$（$0 \le x, y < 2^{30}$）。
我们可以进行 最多 2 次询问，每次询问给出一个整数 $n$（$0 \le n < 2^{30}$），评测机会返回

$$f(n) = (n | x) + (n | y)$$

其中 $|$ 是按位或运算。

两次询问结束后，评测机会再给出一个整数 $m$（$0 \le m < 2^{30}$），我们需要输出

$$\text{ans} = (m | x) + (m | y)$$

---

关键推导

1. 按位分解

对于二进制第 $k$ 位（$k = 0, 1, \dots, 29$），设 $x_k, y_k, n_k \in \{0,1\}$ 表示该位的值。

$(n|x)$ 的第 $k$ 位 = $n_k \ | \ x_k$
$(n|y)$ 的第 $k$ 位 = $n_k \ | \ y_k$

所以该位对 $f(n)$ 的贡献为：

$$c_k = (n_k | x_k) + (n_k | y_k) \in \{0,1,2\}$$

---

2. 一次询问 $n=0$

当 $n=0$ 时，所有位 $n_k = 0$，那么：

$$c_k = x_k + y_k$$

因此：

$$f(0) = \sum_{k=0}^{29} (x_k + y_k) 2^k = x + y$$

记：

$$S = x + y$$

通过第一次询问 $n=0$ 得到 $S$。

---

3. 最终答案公式

对任意 $m$，我们想求：

$$\text{ans} = (m|x) + (m|y)$$

按位分解：

第 $k$ 位贡献：

$$(m_k | x_k) + (m_k | y_k)$$

• 如果 $m_k = 0$：贡献 = $x_k + y_k$
• 如果 $m_k = 1$：贡献 = $1 + 1 = 2$（因为或上 1 必为 1）

因此：

$$\text{ans} = \sum_{k: m_k = 0} (x_k + y_k) 2^k + \sum_{k: m_k = 1} 2 \cdot 2^k $$

第二个和 = $2 \cdot m$（因为 $m = \sum_{k: m_k=1} 2^k$）

第一个和 = $S - \sum_{k: m_k=1} (x_k + y_k) 2^k$

记：

$$T = \sum_{k: m_k=1} (x_k + y_k) 2^k$$

则：

$$\text{ans} = 2m + S - T$$

---

4. 如何求 $T$？

我们需要用第二次询问来求 $T$。

注意到 $T = (m \& x) + (m \& y)$，因为：

• $(m \& x)$ 的第 $k$ 位 = $m_k \cdot x_k$
• $(m \& y)$ 的第 $k$ 位 = $m_k \cdot y_k$
• 所以 $(m \& x) + (m \& y)$ 的第 $k$ 位贡献 = $m_k (x_k + y_k) 2^k$，求和即 $T$。

---

5. 第二次询问的选择

如果我们取 $n = \sim m$（按位取反，即 $n_k = 1 - m_k$，且 $0 \le n < 2^{30}$），则：

对于第 $k$ 位：

• 若 $m_k = 0$，则 $n_k = 1$，贡献 = $(1|x_k)+(1|y_k) = 2$
• 若 $m_k = 1$，则 $n_k = 0$，贡献 = $x_k + y_k$

因此：

$$f(\sim m) = \sum_{k: m_k=0} 2 \cdot 2^k + \sum_{k: m_k=1} (x_k + y_k) 2^k $$

第一个和 = $2 \cdot (\sim m)$，其中 $\sim m$ 表示 $m$ 按位取反（在 $30$ 位意义下，即 $\sim m = (2^{30}-1) - m$）。

第二个和 = $T$。

所以：

$$f(\sim m) = 2 \cdot (\sim m) + T$$

于是：

$$T = f(\sim m) - 2 \cdot (\sim m)$$

---

6. 最终答案公式

代入 $\text{ans} = 2m + S - T$：

$$\text{ans} = 2m + S - [f(\sim m) - 2 \cdot (\sim m)] $$$$\text{ans} = 2m + S - f(\sim m) + 2 \cdot (\sim m) $$

因为 $m + (\sim m) = 2^{30} - 1$，所以：

$$2m + 2 \cdot (\sim m) = 2(m + \sim m) = 2(2^{30} - 1) = 2^{31} - 2 $$

因此：

$$\text{ans} = 2^{31} - 2 + S - f(\sim m)$$

其中 $2^{31} - 2 = 2147483646$。

---

算法步骤

1. 第一次询问：输出 $0$，得到 $S = f(0) = x + y$。
2. 等待评测机给出 $m$（在输出 ! 之后）。
3. 第二次询问：输出 $n = (2^{30} - 1) \oplus m$（即按位取反），得到 $f(\sim m)$。
4. 计算答案：

$$\text{ans} = 2147483646 + S - f(\sim m)$$

5. 输出 $\text{ans}$。

注意：第二次询问是在知道 $m$ 之后进行的，因此仍然在 2 次询问 的限制内。

---

时间复杂度

每个测试用例 $O(1)$ 次询问，总复杂度 $O(t)$，满足 $t \le 10^4$ 的要求。

---

示例验证

以题目第一个测试用例为例：$x=1, y=2, m=1$。

• 第一次询问 $n=0$，得 $S = 1+2 = 3$。

• 收到 $m=1$，计算 $\sim m = (2^{30}-1) \oplus 1 = 2^{30}-2$。

• 第二次询问 $n = 2^{30}-2$，需要知道 $f(2^{30}-2)$ 的值。

  由于 $x=1, y=2$，二进制：

  • $2^{30}-2$ 的二进制：最低位为 0，其余位为 1。
  • $(n|x)$：最低位 = $0|1=1$，其余位 = $1|0=1$（因为 $x$ 除最低位外全 0），所以 $(n|x) = 2^{30}-1$。
  • $(n|y)$：最低位 = $0|0=0$，其余位 = $1|1=1$（因为 $y=2$ 只有第 1 位为 1，其余位 0），所以 $(n|y) = 2^{30}-2$。
  • 和 = $(2^{30}-1) + (2^{30}-2) = 2^{31} - 3$。

• 代入公式：

$$\text{ans} = (2^{31}-2) + 3 - (2^{31}-3) = 4$$

正确。