凯瑟琳在 3 月 8 日收到了一组整数作为礼物。最终她对此感到厌倦,并开始为其计算各种无用的特征。她成功地完成了她想出的每一件作品。但是,当她想出另一个方法时——对数组中所有成对的元素进行异或,她意识到自己无法计算一个非常大的数组,因此她请求您的帮助。你能做到吗?正式地,您需要计算
$$$$$$ (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。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 400\,000$$$) — 数组中整数的数量。
第二行包含整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^7$$$)。
输出
打印单个整数 - 给定数组中所有成对整数和的异或。
示例
输入 #1
2 1 2
输出 #1
3
输入 #2
3 1 2 3
输出 #2
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$$$ 是按位异或运算。要定义 $$$x \oplus y$$$,请考虑整数 $$$x$$$ 和 $$$y$$$ 的二进制表示形式。当 $$$x$$$ 和 $$$y$$$ 的第 $$$i$$$ 位中恰好有一个为 1 时,我们将结果的第 $$$i$$$ 位设置为 1。否则,将结果的第 $$$i$$$ 位设置为 0。例如,$$$0101_2 \, \oplus \, 0011_2 = 0110_2$$$。