/ 
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 は，以下のように定義されます。
- X を 2 進数表記したときの 2^k(0 \leq k, k は整数)の位の値は，c_1, c_2, ...c_m のうち，2 進数表記したときの 2^k の位の値が 1 となるものの個数が奇数個ならば 1，偶数個ならば 0 となります
例えば，3 と 5 のxorの値は，3 の 2 進数表記が 011，5 の 2 進数表記が 101 のため，2 進数表記が 110 の 6 となります。
制約
- 入力は全て整数
- 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