Say xor NO!

Interview

Time limit1sMemory limit1024 MB

Summary

Count the pairs of numbers from two lists whose bitwise XOR is smaller than K.

Level: Medium6 of 10
Topics: Trie, Bit manipulation
Solved: No attempts yet

Problem

Puangi, Chung-Ang University's proud Blue Dragon, has a song he enjoys listening to these days. It is 'Say xor NO!' from 〈Show me the Chung-Ang〉. Puangi fell for the song and made $N$ 'Say' cards and $M$ 'NO!' cards to compute 'Say xor NO!' as the title says.

When a 'Say' card bearing integer $n$ and a 'NO!' card bearing integer $m$ are drawn, the value of the 'Say xor NO!' operation for the two cards is defined as $n \operatorname{xor} m$ .

Puangi, who turns $K$ this year, wonders how many card pairs produce a 'Say xor NO!' result smaller than his age. Write a program to compute that number for Puangi.

Input

The first line gives the number of 'Say' cards $N$ ( $1 \le N \le 100,000$ ), the number of 'NO!' cards $M$ ( $1 \le M \le 100,000$ ), and Puangi's age $K$ ( $1 \le K \le 10^9$ ). The second line gives the numbers $a_1, a_2, \ldots, a_N$ on the 'Say' cards, separated by spaces. The third line gives the numbers $b_1, b_2, \ldots, b_M$ on the 'NO!' cards, separated by spaces. ( $1 \le a_i, b_i \le 10^9$ )

Output

Print the number of card pairs whose bitwise xor result is less than $K$ .

Hint

The definition of the xor operation can be found here.

Examples2

Example 1
Input
```
5 5 6
1 2 3 4 5
3 4 5 6 7
```
Expected output
```
17
```
Example 2
Input
```
5 5 5
1 2 3 4 5
1 1 1 1 1
```
Expected output
```
20
```