310685: CF1870B. Friendly Arrays

B. Friendly Arraystime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given two arrays of integers — $a_1, \ldots, a_n$ of length $n$, and $b_1, \ldots, b_m$ of length $m$. You can choose any element $b_j$ from array $b$ ($1 \leq j \leq m$), and for all $1 \leq i \leq n$ perform $a_i = a_i | b_j$. You can perform any number of such operations.

After all the operations, the value of $x = a_1 \oplus a_2 \oplus \ldots \oplus a_n$ will be calculated. Find the minimum and maximum values of $x$ that could be obtained after performing any set of operations.

Above, $|$ is the bitwise OR operation, and $\oplus$ is the bitwise XOR operation.

Input

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. This is followed by the description of the test cases.

The first line of each test case contains two integers $n$ and $m$ ($1 \leq n, m \leq 2 \cdot 10^5$) — the sizes of arrays $a$ and $b$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 10^9$) — the array $a$.

The third line of each test case contains $m$ integers $b_1, b_2, \ldots, b_m$ ($0 \leq b_i \leq 10^9$) — the array $b$.

It is guaranteed that the sum of values of $n$ and $m$ across all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output $2$ numbers: the minimum and maximum possible values of $x$ after performing any set of operations.

ExampleInput

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

Output

0 1
2 3

Note

In the first test case, if we apply the operation with element $b_1 = 1$, the array $a$ will become $[1, 1]$, and $x$ will be $0$. If no operations are applied, then $x = 1$.

In the second test case, if no operations are applied, then $x = 2$. If we apply the operation with $b_1 = 1$, then $a = [1, 1, 3]$, and $x = 3$.

题目大意：给你两个整数数组a和b，长度分别为n和m。你可以选择数组b中的任意一个元素b_j（1≤j≤m），并对数组a中的所有元素执行a_i = a_i | b_j操作。你可以执行任意次数的此类操作。在所有操作完成后，计算x = a_1 ⊕ a_2 ⊕ ... ⊕ a_n的值。求出在执行任意操作集后，x可能获得的最小值和最大值。

输入数据格式：第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。接下来是t个测试用例的描述。每个测试用例的第一行包含两个整数n和m（1≤n, m≤2×10^5），分别表示数组a和b的长度。第二行包含n个整数a_1, a_2, ..., a_n（0≤a_i≤10^9），表示数组a。第三行包含m个整数b_1, b_2, ..., b_m（0≤b_i≤10^9），表示数组b。保证所有测试用例中n和m的值的总和不超过2×10^5。

输出数据格式：对于每个测试用例，输出两个数字：执行任意操作集后x的最小可能值和最大可能值。题目大意：给你两个整数数组a和b，长度分别为n和m。你可以选择数组b中的任意一个元素b_j（1≤j≤m），并对数组a中的所有元素执行a_i = a_i | b_j操作。你可以执行任意次数的此类操作。在所有操作完成后，计算x = a_1 ⊕ a_2 ⊕ ... ⊕ a_n的值。求出在执行任意操作集后，x可能获得的最小值和最大值。 输入数据格式：第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。接下来是t个测试用例的描述。每个测试用例的第一行包含两个整数n和m（1≤n, m≤2×10^5），分别表示数组a和b的长度。第二行包含n个整数a_1, a_2, ..., a_n（0≤a_i≤10^9），表示数组a。第三行包含m个整数b_1, b_2, ..., b_m（0≤b_i≤10^9），表示数组b。保证所有测试用例中n和m的值的总和不超过2×10^5。 输出数据格式：对于每个测试用例，输出两个数字：执行任意操作集后x的最小可能值和最大可能值。