M-小苯的异或疑惑（hard）_北京信息科技大学第十五届程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

注意，这是此题的 hard 版本，与 easy 版不同的是，本题的 n 最大有 $200000$ 。

小苯有一个数组，长度为 $n$ ，数组下标为 $1$ 到 $n$ 。

他定义了一个函数 $\mathop{f(i, j)}\limits_{1\leq i < j \leq n} = a_i \oplus a_j$ 。
其中 $\oplus$ 表示按位异或运算，对应键盘上的 ^ 符号。
小苯会选出所有合法的 $i$ ， $j$ 对，并求出所有的 $f$ ( $i,j$ ) 值。显然 $n$ 个数字的数组会有 $n \times (n - 1) / 2$ 个 $f$ 函数值。
小苯想问问你，这些 $f$ 函数全部异或起来的值是多少？

换句话说，你需要求出 $f_{1,2} \oplus f_{1,3} \oplus f_{1,4} \oplus ... \oplus f_{2, 3} \oplus f_{2, 4} \oplus ... \oplus f_{n - 1, n}$ 的值是多少。

注意 ^ 表示按位异或运算。

输入描述:

输入包含两行第一行一个正整数  ，表示数组  的长度。
第二行  个整数  ，表示数组  中的元素。

输出描述:

输出包含一行。
一个整数表示所有  函数的值异或起来的结果。

示例1

输入

复制

3
1 1 2

输出

复制

说明

我们考虑所有  对



因此答案为：

备注:

按位异或解释：
对于  ，如果  对应二进制下的位不同，则结果为 ，否则对应二进制的位相同，则结果为 。
例如