题目描述

题目译自 Open Olympiad in Informatics 2020 Day2 T2 「Подарок / Present」。

在三八妇女节，卡特琳娜收到了一份数字数组作为礼物。过了一段时间，她对仅仅盯着数组感到厌倦，于是决定计算一些无用的特征。她成功计算了自己想出的所有特征。然而，当她想到一个新的特征——数组中数字两两之和的异或值时，她发现自己无法为一个大数组计算出这个值，于是请求你的帮助。你能做到吗？更正式地，你需要计算：

$$\begin{aligned} (a_1 + a_2) \oplus (a_1 + a_3) \oplus \ldots \oplus (a_1 + a_n) \oplus \\ \oplus (a_2 + a_3) \oplus \ldots \oplus (a_2 + a_n) \oplus \\ \ldots \\ \oplus (a_{n-1} + a_n) \\ \end{aligned} $$

输入格式

第一行包含一个整数 $n$ $(2 \leq n \leq 400000)$，表示数组中的数字数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 10^{7})$。

输出格式

输出一个数字，即给定数组中两两之和的异或值。

2
1 2

3

在第一个样例中，只有一个和：$1 + 2 = 3$。

3
1 2 3

2

在第二个样例中，有三个和：$1 + 2 = 3$，$1 + 3 = 4$，$2 + 3 = 5$。在二进制下，这是 $011_2 \oplus 100_2 \oplus 101_2 = 010_2$，即 $2$。

$\oplus$ 表示按位异或操作。要确定 $x \oplus y$，考虑数字 $x$ 和 $y$ 的二进制表示。如果 $x$ 和 $y$ 的第 $i$ 位中恰好有一个为 $1$，则结果的第 $i$ 位为 $1$；否则，结果的第 $i$ 位为 $0$。例如，$0101_2 \oplus 0011_2 = 0110_2$。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

子任务	分值	附加限制	子任务依赖	备注
$1$	$34$	$n \leq 1000$	$0$
$2$	$37$	$1 \leq a_i \leq 100$	$0$
$3$	$29$		$0, 1, 2$