CF1322B.Present

Catherine received an array of integers as a gift for March 8. Eventually she grew bored with it, and she started calculated various useless characteristics for it. She succeeded to do it for each one she came up with. But when she came up with another one — xor of all pairwise sums of elements in the array, she realized that she couldn't compute it for a very large array, thus she asked for your help. Can you do it? Formally, you need to compute

$$(a\_1 + a\_2) \\oplus (a\_1 + a\_3) \\oplus \\ldots \\oplus (a\_1 + a\_n) \\\\ \\oplus (a\_2 + a\_3) \\oplus \\ldots \\oplus (a\_2 + a\_n) \\\\ \\ldots \\\\ \\oplus (a\_{n-1} + a\_n) \\\\$$

Here $x \oplus y$ is a bitwise XOR operation (i.e. $x$ ^ $y$ in many modern programming languages). You can read about it in Wikipedia: https://en.wikipedia.org/wiki/Exclusive_or#Bitwise_operation.

凯瑟琳在三八妇女节收到了一个整数数组作为礼物。后来她对此感到厌倦，便开始计算该数组的各种“无用”性质，并且对之前想到的每一种性质都成功地完成了计算。但当她想到另一种性质——数组中所有元素两两之和的异或值时，她意识到对于非常大的数组，自己无法完成计算，因此向你求助。你能帮她解决这个问题吗？形式化地说，你需要计算：

$$(a\_1 + a\_2) \\oplus (a\_1 + a\_3) \\oplus \\ldots \\oplus (a\_1 + a\_n) \\\\ \\oplus (a\_2 + a\_3) \\oplus \\ldots \\oplus (a\_2 + a\_n) \\\\ \\ldots \\\\ \\oplus (a\_{n-1} + a\_n) \\\\$$

其中 $x \oplus y$ 表示按位异或运算（即许多现代编程语言中的 x ^ y）。你可以在维基百科了解该运算：https://en.wikipedia.org/wiki/Exclusive_or#Bitwise_operation。

The first line contains a single integer $n$ ($2 \leq n \leq 400\,000$) — the number of integers in the array.

The second line contains integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^7$).

第一行包含一个整数 $n$（$2 \leq n \leq 400\,000$）—— 表示数组中整数的个数。

第二行包含整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^7$）。

Print a single integer — xor of all pairwise sums of integers in the given array.

输出一个整数——给定数组中所有整数两两之和的异或（xor）值。

In the first sample case there is only one sum $1 + 2 = 3$.

In the second sample case there are three sums: $1 + 2 = 3$, $1 + 3 = 4$, $2 + 3 = 5$. In binary they are represented as $011_2 \oplus 100_2 \oplus 101_2 = 010_2$, thus the answer is 2.

$\oplus$ is the bitwise xor operation. To define $x \oplus y$, consider binary representations of integers $x$ and $y$. We put the $i$-th bit of the result to be 1 when exactly one of the $i$-th bits of $x$ and $y$ is 1. Otherwise, the $i$-th bit of the result is put to be 0. For example, $0101_2 \, \oplus \, 0011_2 = 0110_2$.

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

在第二个样例中，共有三种和：$1 + 2 = 3$、$1 + 3 = 4$、$2 + 3 = 5$。它们的二进制表示分别为 $011_2 \oplus 100_2 \oplus 101_2 = 010_2$，因此答案为 2。

$\oplus$ 表示按位异或（bitwise xor）运算。定义 $x \oplus y$ 时，考虑整数 $x$ 和 $y$ 的二进制表示。当且仅当 $x$ 和 $y$ 的第 $i$ 位中恰好有一个为 1 时，结果的第 $i$ 位为 1；否则，结果的第 $i$ 位为 0。例如，$0101_2 \, \oplus \, 0011_2 = 0110_2$。