题目描述

给定两个长度为 $N$ 的非负整数序列 $a_1,\ldots,a_N$ 和 $b_1,\ldots,b_N$。

对于所有满足 $1 \leq i, j \leq N$ 的整数 $i, j$，一共有 $N^2$ 种选择方式。对于每一种 $i, j$，计算 $a_i + b_j$ 并将其写在纸上。也就是说，纸上会写下 $N^2$ 个整数。

请计算这 $N^2$ 个整数的异或和。

异或的说明

对于整数 $c_1, c_2, \ldots, c_m$，它们的异或和 $X$ 定义如下：

• $X$ 的二进制表示中第 $2^k$ 位（$0 \leq k$，$k$ 为整数）的值，如果 $c_1, c_2, \ldots, c_m$ 中第 $2^k$ 位为 $1$ 的数的个数为奇数，则该位为 $1$，否则为 $0$。

例如，$3$ 和 $5$ 的异或值为 $6$，因为 $3$ 的二进制为 $011$，$5$ 的二进制为 $101$，它们的异或为 $110$，即 $6$。

输入格式

输入以如下格式从标准输入读入。

$N$ $a_1$ $a_2$ $\ldots$ $a_N$ $b_1$ $b_2$ $\ldots$ $b_N$

输出格式

请输出计算得到的结果。

样例 1

输入

2
1 2
3 4

输出

2

样例 2

输入

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

输出

8

样例 3

输入

5
1 2 3 4 5
1 2 3 4 5

输出

2

样例 4

输入

1
0
0

输出

0

说明/提示

限制条件

• 输入均为整数。
• $1 \leq N \leq 200,\!000$
• $0 \leq a_i, b_i < 2^{28}$

样例解释 1

纸上会写下 $4(1+3),\ 5(1+4),\ 5(2+3),\ 6(2+4)$ 共 $2^2 = 4$ 个数。

由 ChatGPT 4.1 翻译