CF1322B Present

Catherine 在三八妇女节收到了一个整数数组作为礼物。后来她对这个数组感到无聊，开始计算各种无用的特性。她成功地计算出了她能想到的每一个特性。但当她想到另一个特性——数组中所有元素两两之和的异或值时，她发现对于非常大的数组，她无法计算出来，于是请求你的帮助。你能做到吗？形式化地说，你需要计算 $$ (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](https://en.wikipedia.org/wiki/Exclusive_or#Bitwise_operation)。

第一行包含一个整数 $n$（$2 \leq n \leq 400\,000$），表示数组中的整数个数。 第二行包含 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^7$）。

输出一个整数，表示给定数组中所有元素两两之和的异或值。

在第一个样例中，只有一个和 $1 + 2 = 3$。 在第二个样例中，有三个和：$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$。 由 ChatGPT 4.1 翻译