AT_arc092_b [ABC091D] Two Sequences
Description
[problemUrl]: https://atcoder.jp/contests/abc091/tasks/arc092_b
$ 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 $ となります。
Input Format
入力は以下の形式で標準入力から与えられる。
> $ N $ $ a_1 $ $ a_2 $ $ ... $ $ a_N $ $ b_1 $ $ b_2 $ $ ... $ $ b_N $
Output Format
求めた結果を出力せよ。
Explanation/Hint
### 制約
- 入力は全て整数
- $ 1\ \leq\ N\ \leq\ 200,000 $
- $ 0\ \leq\ a_i,\ b_i\