← 返回题目列表

AtCoder · arc092_b

D. 两个序列

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

给你两个整数序列,每个序列的长度 N: a_1, ..., a_N 和 b_1, ..., b_N.

有 N^2 选择两个整数的方法 i 和 j 这样 1 \leq i, j \leq N。对于每一个 N^2 对,我们将计算 a_i + b_j 并将其写在一张纸上。 也就是说,我们将写 总共 N^2 个整数。

计算这些的异或 N^2 整数。

异或的定义

整数的异或 c_1, c_2, ..., c_m 定义如下:

  • 让 XOR 为 X。在二进制表示中 X,中的数字 2^k的地点 (0 \leq k; k 是一个整数)是 1 如果其中有奇数个整数 c_1, c_2, ...c_m 其二进制表示有 1 在 2^k的地点,以及 0 如果该数字是偶数。

例如,让我们计算 XOR 3 和 5。的二进制表示 3 is 011,以及二进制表示 5 is 101,因此 XOR 具有二进制表示形式 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

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