P15134 [ROIR 2026] XOR 染色

给定两个非负整数数组 $A=[a_1, a_2, \ldots, a_n]$ 和 $B=[b_1, b_2, \ldots, b_m]$。 定义 $S(i) = \{j | (a_i \oplus b_j) \leq x\}$。换句话说，$S(i)$ 是数组 $B$ 中所有满足 $a_i$ 与 $b_j$ 的按位异或结果不超过 $x$ 的下标 $j$ 的集合。 请求出最小的数字 $k$，使得可以将数组 $A$ 中的元素染成 $k$ 种颜色，且满足：如果 $S(x)$ 与 $S(y)$ 相交，则 $x$ 和 $y$ 必须被染成不同的颜色。 换言之，需要找到 $c_1, c_2, \ldots, c_n$，使得 $1 \le c_i \le k$，并且如果 $S(x) \cap S(y) \neq \varnothing$，则 $c_x \neq c_y$。 提醒一下，两个非负整数的按位“异或”（$\oplus$，xor）定义如下：将两个数写作二进制形式，结果的第 $i$ 个二进制位为 1，当且仅当两个参数中恰好有一个在该位为 1。例如，$(14 \text{ xor } 7) = (1110_2 \oplus 0111_2) = 1001_2 = 9$。该操作在所有现代编程语言中都有实现，在 C++、Java 和 Python 中写作 `^`，在 Pascal 中写作 xor。

此题的输入包含多个测试用例。 输入的第一行包含一个整数 $t$ $(1 \le t \le 100)$ —— 测试用例的数量。 接下来是各个测试用例的描述。 每个测试用例的第一行包含三个整数 $n$、$m$ 和 $x$（$1 \le n, m \le 500\,000$，$0 \leq x < 2^{30}$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ —— 数组 $A$ 的元素（$0 \le a_i < 2^{30}$）。 第三行包含 $m$ 个整数 $b_1, b_2, \ldots, b_m$ —— 数组 $B$ 的元素（$0 \le b_i < 2^{30}$）。 保证所有测试用例的 $n$ 值之和以及 $m$ 值之和均不超过 $500\,000$。

对于每个测试用例，输出一个整数 —— 所求的最小 $k$。

### 评分规则 | 子任务 | 分值 | 额外限制 | 必要子任务 | |:-:|:-:|:-:|:-:| | 1 | 5 | $n \le 2$ | --- | | 2 | 5 | $n \le 5$ | 1 | | 3 | 5 | $n \le 15$ | 1, 2 | | 4 | 5 | $n \le 100$ | 1–3 | | 5 | 5 | $n \le 2\,000$ | 1–4 | | 6 | 10 | $n \le 5\,000$ | 1–5 | | 7 | 5 | $n \le 100\,000$，$m = 2$ | --- | | 8 | 10 | $n \leq 100\,000$，$m = 3$ | --- | | 9 | 5 | $n, m \le 100\,000$；$a_i, b_i, k < 2$ | --- | | 10 | 10 | $n, m \le 100\,000$；$a_i, b_i, k < 4$ | 9 | | 11 | 35 | 无额外限制 | 1–10 |