D - Two Sequences

Time Limit: 3 sec / Memory Limit: 256 MB

配点 : 500

問題文

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の説明

整数 c_1, c_2, ..., c_m のxor X は,以下のように定義されます。

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

例えば,35 のxorの値は,32 進数表記が 01152 進数表記が 101 のため,2 進数表記が 1106 となります。

制約

  • 入力は全て整数
  • 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

紙には 4(1+3), 5(1+4), 5(2+3), 6(2+4)2^2 = 4 つの数が書かれます。


入力例 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