Permutation from two arrays

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Marichka has 2 arrays of integers: array \(a\) of \(n\) elements and array \(b\) of \(m\) elements, where \(n\) and \(m\) are odd.

Marichka wants to choose a number \(x\) and replace all values of \(a_i\) with \(a_i\) \(XOR\) \(x\). Then Zenyk similarly wants to choose a number \(y\) and replace all values of \(b_i\) with \(b_i\) \(XOR\) \(y\).

Afterwards, Marichka and Zenyk merge both arrays into one and want the resulting array to be a permutation of numbers from 0 to \(n + m - 1\). That is, all values must be distinct integers within the range \([0, n+m-1]\).

Help them find how many ways there are to choose a pair of values \(x\) and \(y\) to satisfy these conditions.

Input

The first line contains 2 integers \(n\) and \(m\) — the sizes of the arrays.

The second line contains \(n\) integers \(a_i\).

The third line contains \(m\) integers \(b_i\).

Output

Output a single number — the number of possible pairs \(x\) and \(y\).

Constraints

\(1 \le n, m \le 2 \cdot 10^5\), \(n\) and \(m\) are odd,

\(0 \le a_i, b_i \le 10^6\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 3 3 4 7 7 4 3	2

Input (stdin) сopy	Output (stdout) сopy
1 3 47 7 4 7	0

Notes

In the first example, you can choose \(x=7\), \(y=6\) or vice versa.