题目描述

给定一个长度为 $n$ 的数列 $a_1,a_2,\cdots,a_n$，计算这个序列所有连续子序列的和的异或值，也就是计算

$$\bigoplus_{1\leq i\leq j\leq n} \{ a_i+a_{i+1}+\cdots+a_{j-1}+a_{j} \} $$

其中 $\oplus$ 表示异或运算。例如对于数列 $20,10,35$，有六个子序列，它们的和分别是：$20$、$10$、$35$、$20+10$、$10+35$、$20+10+35$，它们的异或和为 $79$。

输入格式

第一行：单个整数 $n$； 第二行：$n$个整数表示 $a_1,a_2,\cdots,a_n$。

输出格式

单个整数：所有连续子序列的和的异或值。

3
20 10 35

79

数据范围

• $0\leq a_i$；
• $a_1+a_2+\cdots+a_n\leq 1,000,000$；
• 对于 $30\%$ 的数据，$1\leq n \leq 10^3$；
• 对于 $60\%$ 的数据，$1\leq n \leq 10^4$；
• 对于 $100\%$ 的数据，$1\leq n \leq 10^5$。