← 返回题目列表

Codeforces · 1721/D

D. 最大与

中文机器翻译题面 查看原题

给定两个数组 $$$a$$$ 和 $$$b$$$,每个数组由 $$$n$$$ 整数组成。

让我们定义一个函数 $$$f(a, b)$$$ 如下:

- 让我们定义一个大小为 $$$n$$$ 的数组 $$$c$$$,其中 $$$c_i = a_i \oplus b_i$$$ ($$$\oplus$$$ 表示按位异或);
- 函数的值为 $$$c_1 \mathbin{\&} c_2 \mathbin{\&} \cdots \mathbin{\&} c_n$$$ (即整个数组 $$$c$$$ 的按位 AND)。

如果您可以以任意方式对数组 $$$b$$$ 重新排序(也可以选择保留初始顺序),请找到函数 $$$f(a, b)$$$ 的最大值。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组 $$$a$$$ 和 $$$b$$$ 的大小。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < 2^{30}$$$)。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_i < 2^{30}$$$)。

所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印一个整数 - 如果您可以以任意方式对数组 $$$b$$$ 重新排序,则函数 $$$f(a, b)$$$ 的最大值。

示例

输入 #1

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

输出 #1

2
0
7