← 返回题目列表

Codeforces · 1870/B

B. 友好数组

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

给定两个整数数组 — $$$a_1, \ldots, a_n$$$,长度为 $$$n$$$,以及 $$$b_1, \ldots, b_m$$$,长度为 $$$m$$$。您可以从数组 $$$b$$$ ($$$1 \leq j \leq m$$$) 中选择任何元素 $$$b_j$$$,并对所有 $$$1 \leq i \leq n$$$ 执行 $$$a_i = a_i | b_j$$$。您可以执行任意数量的此类操作。

全部运算完成后,将计算出 $$$x = a_1 \oplus a_2 \oplus \ldots \oplus a_n$$$ 的值。找出执行任意一组操作后可获得的 $$$x$$$ 的最小值和最大值。

上面,$$$|$$$ 是按位或运算,$$$\oplus$$$ 是按位异或运算。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。接下来是测试用例的描述。

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

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — 数组 $$$a$$$。

每个测试用例的第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$0 \leq b_i \leq 10^9$$$) — 数组 $$$b$$$。

保证所有测试用例中 $$$n$$$ 和 $$$m$$$ 的值之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$2$$$ 数字:执行任何一组操作后 $$$x$$$ 的最小和最大可能值。

示例

输入 #1

2
2 3
0 1
1 2 3
3 1
1 1 2
1

输出 #1

0 1
2 3

注意

在第一个测试用例中,如果我们对元素 $$$b_1 = 1$$$ 进行运算,则数组 $$$a$$$ 将变为 $$$[1, 1]$$$,$$$x$$$ 将变为 $$$0$$$。如果未应用任何操作,则 $$$x = 1$$$。

在第二个测试用例中,如果未应用任何操作,则 $$$x = 2$$$。如果我们使用 $$$b_1 = 1$$$ 进行运算,则 $$$a = [1, 1, 3]$$$,并且 $$$x = 3$$$。