G. Grand XOR Counting Problem Challenge II
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

The annual GXCPC (Grand XOR Counting Problem Challenge) is here again! This year, Judge Colin has prepared another super difficult counting problem for the contestants! Can you slay this ultimate counting problem and win the championship?

Eva has two magic parameters $$$k_1$$$ and $$$k_2$$$.

Colin has two integer sequences $$$a_1,a_2,\cdots,a_n$$$ and $$$b_1,b_2,\cdots,b_n$$$.

They want to know how many pairs of indices $$$(i,j)$$$ satisfy:

  • $$$1\le i \lt j\le n$$$
  • $$$k_1 \oplus a_i \oplus a_j \lt k_2 \oplus b_i \oplus b_j$$$

Where $$$\oplus$$$ represents the bitwise XOR operation.

Input

The first line contains three integers $$$n,k_1,k_2~(1\le n\le 2\times 10^5,1\le k_1,k_2 \lt 2^{30})$$$, representing the length of the two sequences and the magic parameters.

The second line contains $$$n$$$ integers $$$a_1,a_2,\cdots,a_{n}\ (1\le a_i \lt 2^{30})$$$, representing the first sequence.

The third line contains $$$n$$$ integers $$$b_1,b_2,\cdots,b_{n}\ (1\le b_i \lt 2^{30})$$$, representing the second sequence.

Output

A single integer, representing the number of pairs satisfying the condition.

Example
Input
5 1 2
3 4 5 6 7
1 2 3 1 2
Output
2
Note

There are two valid pairs in the sample: $$$(2,3)$$$ and $$$(4,5)$$$