Fran 最近学习了异或（xor）运算，对于两个整数 $x$ 和 $y$，该运算通过按位异或（exclusive or）返回结果。异或运算记作 $\oplus$，它比较数字 $x$ 和 $y$ 的对应位，并根据以下规则设置结果的每一位：
- 如果对应位置的位不同（0 和 1，或 1 和 0），则结果位为 1。
- 如果位相同（0 和 0，或 1 和 1），则结果位为 0。
例如，对于 $x = 5$ 和 $y = 3$，二进制表示为：$x = 101_2, y = 011_2$。对对应位应用异或运算得到 $x \oplus y = 101_2 \oplus 011_2 = 110_2 = 6$。换句话说，$5 \oplus 3 = 6$。
Fran 得到了一个包含 $n$ 个整数的数组 $a_1, a_2, \dots, a_n$，并决定进行以下操作：
- 对于每一对满足 $1 \le i \le j \le n$ 的下标 $(i, j)$，计算它们的和 $a_i + a_j$。
- 现在他想要计算所有得到的和的异或结果。
请帮助 Fran 计算所需的结果。
输入格式
第一行包含一个整数 $n$ ($1 \le n \le 5 \cdot 10^5$)，表示数组的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i < 2^{30}$)，如题目描述中所述。
输出格式
在唯一的一行输出中，打印所需的结果。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 7 | $n \le 2000$ |
| 2 | 17 | 对所有 $i$，$a_i < 2^{10}$ |
| 3 | 45 | $n \le 10^5$ |
| 4 | 21 | 无附加限制 |
样例
输入格式 1
3 2 4 5
输出格式 1
14
说明
和为 $2 + 2 = 4, 2 + 4 = 6, 2 + 5 = 7, 4 + 4 = 8, 4 + 5 = 9$ 以及 $5 + 5 = 10$。结果为 $4 \oplus 6 \oplus 7 \oplus 8 \oplus 9 \oplus 10 = 14$。
输入格式 2
4 6 7 3 1
输出格式 2
3
输入格式 3
7 2 3 5 7 9 11 13
输出格式 3
6