K. K-MEX

time limit per test: 1 second

memory limit per test: 512 megabytes

input: standard input

output: standard output

Let $a$ be an array of length $n$. Define $\operatorname{mex}(a)$ as the smallest non-negative integer that does not appear in $a$. For example:

• $\operatorname{mex}([4, 0, 2, 1]) = 3$
• $\operatorname{mex}([-2, -4, 3]) = 0$

Define a $k$-transformation as follows: for each index $i$ ($1 \leq i \leq n$), independently choose to either keep $a_i$ unchanged or replace it with $k - a_i$. After all choices are made, we obtain a new array $a'$.

Define $k$-$\operatorname{mex}(a)$ as the maximum possible value of $\operatorname{mex}(a')$ among all arrays $a'$ that can be obtained from $a$ via a $k$-transformation.

You must answer $q$ queries. Each query provides a non-negative integer $k$; compute $k$-$\operatorname{mex}(a)$ for each query.

To reduce the output size, you are only required to output the bitwise XOR (exclusive-OR) of the answers over all $q$ queries.

Input

The first line contains a single integer $T$ ($1 \leq T \leq 10^3$), denoting the number of test cases.

For each test case:

• The first line contains a single positive integer $n$ ($1 \leq n \leq 5 \times 10^3$), denoting the length of the array.
• The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \leq a_i \leq 10^9$), denoting the initial elements of array $a$.
• The next line contains a single positive integer $q$ ($1 \leq q \leq 5 \times 10^5$), denoting the number of queries.
• Each of the next $q$ lines contains a single non-negative integer $k$ ($0 \leq k \leq 10^9$), denoting you must compute $k$-$\operatorname{mex}(a)$ for this $k$.

It is guaranteed that $\sum n \leq 5 \times 10^3$ and $\sum q \leq 5 \times 10^5$ across all test cases in one test file.

Output

For each test case, output a single integer, denoting the bitwise XOR (exclusive-OR) of the answers to all queries in that test case.

Example

Input

2
3
0 1 3
3
1
2
5
9
0 0 1 1 2 3 3 4 5
7
4
5
6
7
8
9
10

Output

3
8

Note

For the first test case:

• For the query $k=1$, replacing $a_i$ with $k-a_i$ for $i=1,2$ gives $a'=[1,0,3]$, whose $\operatorname{mex}$ is $2$. Moreover, no $k$-transformation can make $2$ appear in $a'$, so its $\operatorname{mex}$ cannot exceed $2$. Therefore, $k$-$\operatorname{mex}(a)=2$.
• For the query $k=2$, the only element that can become either $0$ or $2$ is $a_1=0$, so these two values cannot both appear in $a'$ after any $k$-transformation. Taking $a'=[0,1,3]$ gives $\operatorname{mex}(a')=2$, so $k$-$\operatorname{mex}(a)=2$.
• For the query $k=5$, replacing $a_3$ with $k-a_3$ gives $a'=[0,1,2]$. Since the array has length $3$, its $\operatorname{mex}$ cannot exceed $3$. Therefore, $k$-$\operatorname{mex}(a)=3$.

Thus, the bitwise XOR of the answers to the three queries is $2\mathbin{\mathtt{\oplus}}2\mathbin{\mathtt{\oplus}}3=3$.

For the second test case, the answers to the queries $k=4,5,6,7,8,9,10$ are $6,6,7,8,6,7,6$, respectively, and their bitwise XOR is $8$.

题解

这道题是一道非常精妙的 MEX 性质分析 + 贪心匹配 的算法题。下面为你带来这道题的详细分析与题解。

---

一、 题目大意回顾

给定一个长度为 $n$ 的非负整数数组 $a$。
对于给定的整数 $k$，$k$-变换允许我们将每个元素 $a_i$ 独立地替换为 $a_i$ 或 $k - a_i$。
定义 $k\text{-}\operatorname{mex}(a)$ 为变换后数组 $a'$ 所能达到的最大 $\operatorname{mex}$ 值。
有 $q$ 次询问，每次给出一个 $k$，要求输出所有询问答案的异或和（XOR sum）。

数据范围：$\sum n \le 5 \times 10^3$，$\sum q \le 5 \times 10^5$。

---

二、 核心性质与突破口

性质 1：答案的天然下界

如果不做任何变换（即对所有 $i$ 都保留 $a'_i = a_i$），数组的 $\operatorname{mex}$ 就是原数组的 $\operatorname{mex}$。
设原数组的 $\operatorname{mex}$ 为 $M = \operatorname{mex}(a)$。
那么无论 $k$ 是多少，我们至少能达到 $M$：
$$k\text{-}\operatorname{mex}(a) \ge M$$

性质 2：绝大多数 $k$ 的答案都严格等于 $M$（最核心剪枝）

根据 MEX 的定义：

• 在原数组 $a$ 中，数 $0, 1, \dots, M-1$ 都存在。
• 数 $M$ 在原数组中不存在。

如果要使得变换后的 $\operatorname{mex}(a') > M$，那么 数 $M$ 必须出现在变换后的数组 $a'$ 中。
因为原数组中没有任何数等于 $M$，所以 $M$ 只能通过某个数变换得到：
$$k - a_i = M \iff k = M + a_i$$

重要结论：

如果某个 $k$ 不能写成 $M + a_i$（其中 $a_i \in a$）的形式，那么无论怎么选择变换，$M$ 都绝对不可能出现在新数组中！
这意味着 $\operatorname{mex}(a')$ 绝不可能超过 $M$。
结合性质 1，我们得出：对于所有不属于 $\{M + a_i \mid a_i \in a\}$ 的 $k$，其答案必然严格等于 $M$！

因为数组长度为 $n$，所以可能让答案大于 $M$ 的 $k$ 最多只有 $n$ 个！
对于其它所有询问，答案直接就是 $M$。

性质 3：MEX 的理论上限

数组长度为 $n$。一个长度为 $n$ 的数组最多包含 $n$ 个不同的数。
由鸽巢原理，$0, 1, \dots, n$ 中至少有一个数不在数组中，因此：
$$\operatorname{mex}(a') \le n$$
所以我们只需要关心 $[0, n-1]$ 范围内的数是否能被覆盖，大于等于 $n$ 的数对提高 MEX 毫无用处。

---

三、 单个候选 $k$ 的贪心求解

对于某个候选的 $k$（形如 $k = M + a_i$），如何求出最大的 $\operatorname{mex}$？

1. 独立等价类分析

每个元素 $a_i$ 只能变成 $a_i$ 或 $k - a_i$。
notice 到：

• 值为 $x$ 的元素只能变成 $x$ 或 $k - x$。
• 值为 $k - x$ 的元素只能变成 $k - x$ 或 $x$。
• 它们完全无法变成其它任何值！

也就是说，所有数值自动划分成了独立的数对 $\{x, k - x\}$：

• 属于数对 $\{x, k - x\}$ 的元素总数是固定的。
• 要覆盖 $x$，需要从该数对中至少消耗 1 个元素。
• 要同时覆盖 $x$ 和 $k - x$（当 $x \neq k - x$ 时），需要该数对中至少有 2 个元素。

2. 贪心策略

由于我们希望 MEX 尽量大，目标是按顺序依次凑出 $0, 1, 2, \dots$：

1. 先统计能为 $[0, n-1]$ 提供贡献的元素数量，存入计数数组 c：
   • 若 $v < n$，它本身就可以作为 $v$，放入 c[v]++；
   • 若 $v \ge n$ 但 $k - v \in [0, n-1]$，它虽然自己用不上，但可以变成 $k - v$，放入 c[k - v]++。
2. 从 $x = 0$ 开始递增检查：
   • 能否凑出 $x$？
     • 首先看 c[x] 是否 $> 0$（使用本身就是 $x$ 的数，或由 $v \ge n$ 变换过来的数）；
     • 若 c[x] == 0，再看 c[k - x] 是否 $> 0$（将原本在 $[0, n-1]$ 范围内的 $k-x$ 翻转为 $x$）；
     • 若两者都没有，说明无论如何也凑不出 $x$，循环终止，当前 $x$ 即为最大 MEX；
     • 若凑出了 $x$，将对应计数减 $1$，然后继续检验 $x + 1$。

为什么这个贪心是正确的？
因为当我们检验较小的数 $x$ 时，它与 $k - x$ 共享同一个元素池。任何属于这个池的元素都可以当 $x$ 或当 $k - x$ 用。无论消耗哪一个，池子剩余的元素数量都是一样的，留给后续 $k - x$ 的机会也是完全相等的。所以贪心地优先满足更小的数 $x$ 是全局最优的。

---

四、 查询的异或性质技巧

题目要求对所有查询的答案求异或和：

• 异或满足自反性：$A \oplus A = 0$。
• 如果同一个 $k$ 出现了偶数次，它们的结果相互抵消为 $0$。
• 因此题解代码中使用了 set<int> sq：

  auto [it, inserted] = sq.insert(K);
  if (!inserted) {
      sq.erase(it); // 如果已经存在，说明出现了偶数次，直接删除抵消
  }
  

  这样只需保留出现奇数次的 $k$。

最终计算异或和：

• 如果 $K$ 在预计算的候选字典 f 中，异或其真实算出的最大 MEX；
• 如果不在 f 中，由性质 2 可知答案就是原数组的 mex，直接异或 mex。

---

五、 核心代码逐段详解

#include <bits/stdc++.h>
namespace rgs = std::ranges;
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;

        map<int, int> cnt;
        vector<int> A;
        for (int i = 0; i < N; i++) {
            int x;
            cin >> x;
            cnt[x]++;
            A.push_back(x);
        }
        rgs::sort(A);

        int Q;
        cin >> Q;

        // 利用 set 去除偶数次重复的查询（偶数次异或为0）
        set<int> sq;
        while (Q--) {
            int K;
            cin >> K;
            auto [it, inserted] = sq.insert(K);
            if (!inserted) {
                sq.erase(it);
            }
        }
        vector<int> queries(sq.begin(), sq.end());
        
        // 1. 求出原数组的 mex
        int mex = 0;
        while (cnt.contains(mex)) {
            mex++;
        }

        // 2. 仅对 k = mex + v (v in A) 进行计算
        map<int, int> f;
        for (auto v : A) {
            int k = mex + v;
            if (f.contains(k)) continue; // 避免重复计算相同的 k

            vector<int> c(N);
            // 统计能贡献到 [0, N-1] 的元素
            for (auto val : A) {
                if (val < N) {
                    c[val]++;
                } else if (k - val >= 0 && k - val < N) {
                    c[k - val]++;
                }
            }

            // 贪心检验能连续凑出多大的数
            int x = 0;
            while (true) {
                if (x < N && c[x]) {
                    c[x]--;
                } else if (k - x >= 0 && k - x < N && c[k - x]) {
                    c[k - x]--;
                } else {
                    break; // 凑不出 x，停止
                }
                x++;
            }
            f[k] = x;
        }

        // 3. 统计异或和
        int ans = 0;        
        for (auto K : queries) {
            if (f.contains(K)) {
                ans ^= f[K];      // 特殊候选 k 的答案
            } else {
                ans ^= mex;       // 其他 k 的答案必定为原数组的 mex
            }
        }
        cout << ans << "\n";
    }

    return 0;
}

---

六、 复杂度分析

1. 预处理与候选 $k$ 的计算：

   • 候选 $k$ 最多有 $N$ 个。
   • 对每个候选 $k$，初始化 c 数组耗时 $O(N)$，贪心循环最多执行 $N$ 次，耗时 $O(N)$。
   • 总体候选计算时间为 $O(N^2)$。
   • 数据保证 $\sum N \le 5000$，最坏情况下 $\sum N^2 \le (5000)^2 = 2.5 \times 10^7$，在 C++ 中耗时仅几十毫秒。

2. 询问处理：

   • 使用 std::set 去重抵消奇偶次数：$O(Q \log Q)$。
   • 查询答案并异或：$O(Q \log N)$。
   • 数据保证 $\sum Q \le 5 \times 10^5$，运算次数在 $10^7$ 级别，耗时约 $0.2 \sim 0.3$ 秒。

总时间复杂度：$O(N^2 + Q \log Q)$，完全能在 1.0 秒的时限内轻松通过。
空间复杂度：$O(N + Q)$，空间消耗极小。