Maximum AND
Contest: Educational Codeforces Round 134 (Rated for Div. 2)
Difficulty rating: 1800
Tags: bitmasks, dfs and similar, divide and conquer, greedy, sortings

You are given two arrays $$$a$$$ and $$$b$$$, consisting of $$$n$$$ integers each.

Let's define a function $$$f(a, b)$$$ as follows:

- let's define an array $$$c$$$ of size $$$n$$$, where $$$c_i = a_i \oplus b_i$$$ ($$$\oplus$$$ denotes bitwise XOR);
- the value of the function is $$$c_1 \mathbin{\&} c_2 \mathbin{\&} \cdots \mathbin{\&} c_n$$$ (i.e. bitwise AND of the entire array $$$c$$$).

Find the maximum value of the function $$$f(a, b)$$$ if you can reorder the array $$$b$$$ in an arbitrary way (leaving the initial order is also an option).

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the size of arrays $$$a$$$ and $$$b$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < 2^{30}$$$).

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_i < 2^{30}$$$).

The sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case print one integer — the maximum value of the function $$$f(a, b)$$$ if you can reorder the array $$$b$$$ in an arbitrary way.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
3
5
1 0 0 3 3
2 3 2 1 0
3
1 1 1
0 0 3
8
0 1 2 3 4 5 6 7
7 6 5 4 3 2 1 0

Example output:
2
0
7

Editorial:
We will build the answer greedily, from the highest significant bit to the lowest one. Let's analyze how to check if the answer can have the highest bit equal to $$$1$$$. It means that every value in $$$c$$$ should have its highest bit equal to $$$1$$$, so for every $$$i$$$, exactly one of the numbers $$$\{a_i, b_i\}$$$ should have this bit equal to $$$1$$$. For both of the given arrays, we can calculate how many elements have which value of this bit, and then the number of elements with $$$1$$$ in this bit in the array $$$a$$$ should be equal to the number of elements with $$$0$$$ in the array $$$b$$$ (and the same for elements with $$$0$$$ in $$$a$$$ and elements with $$$1$$$ in $$$b$$$). If these values are equal, it means that the elements of $$$a$$$ and $$$b$$$ can be matched in such a way that in every pair, the XOR of them has $$$1$$$ in this bit. If it is so, then the highest bit of the answer is $$$1$$$, otherwise it is $$$0$$$.
Okay, then let's proceed to the next bit. Should we just do the same to check if this bit can be equal to $$$1$$$ in the answer? Unfortunately, that's not enough. Let's look at the case: $$$a = [3, 0]$$$, $$$b = [2, 1]$$$. We can get the value $$$1$$$ in the $$$0$$$-th bit or in the $$$1$$$-st bit, but not in both simultaneously. So, for the next bit, we need to make sure that not only we can get $$$1$$$ in the result, but we can also do this without transforming some of the $$$1$$$-s to $$$0$$$-s in the higher bits. If it is impossible, it doesn't matter if we can get $$$1$$$ in the current bit since it will be suboptimal, so we have to use an ordering that gets $$$0$$$ in this bit.
In general case, it means that we have to solve the following subproblem: check if we can obtain $$$1$$$ in several bits of the answer; let these bits be $$$\{x_1, x_2, \dots, x_k\}$$$ ($$$x_1$$$ to $$$x_{k-1}$$$ are the bits that we have already checked; $$$x_k$$$ is the new bit we are trying to check). Let $$$mask$$$ be the number that has $$$1$$$ in every bit $$$x_i$$$ and $$$0$$$ in every other bit. The elements should be matched in such a way that $$$(a_i \& mask) \oplus (b_i \& mask) = mask$$$. If we group all numbers from $$$a$$$ and from $$$b$$$ according to the value of $$$a_i \& mask$$$ (or $$$b_i \& mask$$$), then for every group of elements from $$$a$$$, there is a corresponding group in $$$b$$$ such that we can match the elements from the first group only with the elements from the second group. So, if for every such group, its size in $$$a$$$ is equal to the size of the corresponding group in $$$b$$$, then we can set all bits from $$$\{x_1, x_2, \dots, x_k\}$$$ to $$$1$$$ simultaneously.
Some implementation notes: if the number of bits we need to check is big, the number of groups can become too large to handle all of them (since it is $$$2^k$$$). So, to store the number of elements in each group, we should use some associative data structure, like, for example, std::map in C++. If you use a map, splitting elements into groups will be done in $$$O(n \log n)$$$, so in total, you will get complexity of $$$O(n \log n \log A)$$$, where $$$A$$$ is the maximum possible value in the input.