Statement is not available in English language
D. XOR Раскраска
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны два массива неотрицательных целых чисел $$$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)$$$ это множество всех индексов $$$j$$$ массива $$$B$$$, для которых побитовое исключающее или $$$a_i$$$ и $$$b_j$$$ не превосходит $$$x$$$.

Найдите минимальное число $$$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$$$ xor $$$7$$$) = ($$$1110_2 \oplus 0111_2$$$) = $$$1001_2$$$ = $$$9$$$. Эта операция реализована во всех современных языках программирования, в языках C++, Java и Python она записывается как «^{}», в Паскале как «xor».

Входные данные

Входные данные для этой задачи содержат несколько тестовых примеров.

Первая строка ввода содержит одно целое число $$$t$$$ $$$(1 \le t \le 100)$$$ — количество тестовых примеров.

Далее следуют описания тестовых примеров.

В первой строке каждого тестового примера записаны три целых числа $$$n$$$, $$$m$$$ и $$$x$$$ ($$$1 \le n, m \le 500\,000$$$, $$$0 \leq x \lt 2^{30}$$$).

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ — элементы массива $$$A$$$ ($$$0 \le a_i \lt 2^{30}$$$).

В третьей строке записаны $$$m$$$ целых чисел $$$b_1, b_2, \ldots, b_m$$$ — элементы массива $$$B$$$ ($$$0 \le b_i \lt 2^{30}$$$).

Гарантируется, что как сумма значений $$$n$$$, так и сумма значений $$$m$$$ по всем тестовым примерам не превосходит $$$500\,000$$$.

Выходные данные

Для каждого тестового примера выведите одно целое число — минимальное искомое $$$k$$$.

Система оценки
ПодзадачаБаллыДоп. ограниченияНеобх. подзадачи
15$$$n \le 2$$$—
25$$$n \le 5$$$1
35$$$n \le 15$$$1,2
45$$$n \le 100$$$1–3
55$$$n \le 2\,000$$$1–4
610$$$n \le 5\,000$$$1–5
75$$$n \le 100\,000$$$, $$$m = 2$$$—
810$$$n \leq 100\,000$$$, $$$m = 3$$$—
95$$$n, m \le 100\,000$$$; $$$a_i, b_i, klt; 2$$$—
1010$$$n, m \le 100\,000$$$; $$$a_i, b_i, klt; 4$$$9
1135нет1–10
Пример
Входные данные
3
2 2 0
0 0
1 1
5 5 3
0 1 2 3 4
0 1 2 3 4
5 5 4
0 1 2 3 4
0 1 2 3 4
Выходные данные
1
4
5