Contest Duration: - (local time) (100 minutes) Back to Home
D - Two Sequences /

Time Limit: 3 sec / Memory Limit: 256 MB

### 問題文

2 つの長さ N の非負整数列 a_1, ..., a_N, b_1, ..., b_N が与えられます。

1 \leq i, j \leq N となるように整数 i, j を選ぶ方法は N^2 通りありますが，この N^2 通りの i, j それぞれについて，a_i + b_j を計算し，紙に書き出します。 つまり，紙に N^2 個の整数を書きます。

この N^2 個の整数のxorを計算してください。

xorの説明

• X2 進数表記したときの 2^k(0 \leq k, k は整数)の位の値は，c_1, c_2, ...c_m のうち，2 進数表記したときの 2^k の位の値が 1 となるものの個数が奇数個ならば 1，偶数個ならば 0 となります

### 制約

• 入力は全て整数
• 1 \leq N \leq 200,000
• 0 \leq a_i, b_i < 2^{28}

### 入力

N
a_1 a_2 ... a_N
b_1 b_2 ... b_N


### 入力例 1

2
1 2
3 4


### 出力例 1

2


### 入力例 2

6
4 6 0 0 3 3
0 5 6 5 0 3


### 出力例 2

8


### 入力例 3

5
1 2 3 4 5
1 2 3 4 5


### 出力例 3

2


### 入力例 4

1
0
0


### 出力例 4

0


Score : 500 points

### Problem Statement

You are given two integer sequences, each of length N: a_1, ..., a_N and b_1, ..., b_N.

There are N^2 ways to choose two integers i and j such that 1 \leq i, j \leq N. For each of these N^2 pairs, we will compute a_i + b_j and write it on a sheet of paper. That is, we will write N^2 integers in total.

Compute the XOR of these N^2 integers.

Definition of XOR

The XOR of integers c_1, c_2, ..., c_m is defined as follows:

• Let the XOR be X. In the binary representation of X, the digit in the 2^k's place (0 \leq k; k is an integer) is 1 if there are an odd number of integers among c_1, c_2, ...c_m whose binary representation has 1 in the 2^k's place, and 0 if that number is even.

For example, let us compute the XOR of 3 and 5. The binary representation of 3 is 011, and the binary representation of 5 is 101, thus the XOR has the binary representation 110, that is, the XOR is 6.

### Constraints

• All input values are integers.
• 1 \leq N \leq 200,000
• 0 \leq a_i, b_i < 2^{28}

### Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N
b_1 b_2 ... b_N


### Output

Print the result of the computation.

### Sample Input 1

2
1 2
3 4


### Sample Output 1

2


On the sheet, the following four integers will be written: 4(1+3), 5(1+4), 5(2+3) and 6(2+4).

### Sample Input 2

6
4 6 0 0 3 3
0 5 6 5 0 3


### Sample Output 2

8


### Sample Input 3

5
1 2 3 4 5
1 2 3 4 5


### Sample Output 3

2


### Sample Input 4

1
0
0


### Sample Output 4

0