Description

Given two sequences $a, b$, both sorted in non-decreasing order. It is guaranteed that there are no duplicate numbers in $a$.

Now, for each number in $a$, determine how many times it appears in $b$.

Input Format

There are multiple test cases in a single test file.

The first line contains an integer $T$, the number of test cases. Then, for each test case, the input is given as follows:

• The first line contains two integers, the lengths of sequences $a$ and $b$, denoted by $n$ and $m$.
• The second line contains $n$ integers representing sequence $a$, where the $i$-th integer is $a_i$.
• The third line contains $m$ integers representing sequence $b$, where the $i$-th integer is $b_i$.

Output Format

To avoid excessive output, for each test case, output a single integer on one line: the bitwise XOR sum of the occurrence counts of every number of $a$ in $b$.

Formally, let $a_i$ appear $c_i$ times in $b$. You need to output $c_1 \bigoplus c_2 \bigoplus \dots \bigoplus c_n$, where $\bigoplus$ denotes the bitwise XOR operation. You may refer to the Hint to complete the computation.

1
3 5
1 3 6
1 3 3 5 5

3

1
9 4
1 2 3 4 5 6 7 8 9
1 1 4 5

2

2
3 5
1 3 6
1 3 3 5 5
9 4
1 2 3 4 5 6 7 8 9
1 1 4 5

3
2

Hint

Explanation of Sample 1

• $a_1 = 1$ appears $1$ time in $b$.
• $a_2 = 3$ appears $2$ times in $b$.
• $a_3 = 6$ appears $0$ times in $b$.

Therefore, the output is $1 \bigoplus 2 = 3$.

Explanation of Sample 2

$1, 4, 5$ appear $2, 1, 1$ times in $b$, respectively, so the output is $2 \bigoplus 1 \bigoplus 1 = 2$.

Constraints

For all test files, it is guaranteed that:

• $1 \leq T \leq 10$;
• $1 \leq n, m \leq 10^7$, and $\sum (n + m) \leq 10^7$;
• $1 \leq a_i, b_i < 2^{64}$, and $a_i < a_{i + 1}$, $b_i \leq b_{i + 1}$.

Here, $\sum (n + m)$ denotes the sum of all $n$ and $m$ within a single test file, i.e., the total length of the input sequences does not exceed $10^7$.

Notes

• Pay attention to the impact of large input on program efficiency. Choose an appropriate input method to avoid timeouts.
• Use suitable data types to store variables to avoid overflow.
• If you do not know what a bitwise XOR sum is, you can add the following function to your code:

template <class T>
T getXorSum(T *begin, T *end) {
  T ret = 0;
  for (T *it = begin; it != end; ++it) ret ^= *it;
  return ret;
}

This function computes the bitwise XOR sum over a half-open interval of the given array (including std::vector). The return type matches the type of the input array. The usage is similar to std::sort. For example, to compute the bitwise XOR sum of $a_1 \sim a_n$, call getXorSum(a + 1, a + 1 + n). To compute the bitwise XOR sum of $a_0 \sim a_{n - 1}$, call getXorSum(a, a + n). If $a$ is a std::vector, replace a in the calls above with a.begin() accordingly.

Translated by ChatGPT 5