[TJOI2017]异或和

题目描述

在加里敦中学的小明最近爱上了数学竞赛,很多数学竞赛的题都是与序列的连续和相关的。 所以对于一个序列,求出它们所有的连续和来说,小明觉得十分的简单。 但今天小明遇到了一个序列和的难题,这个题目不仅要求你快速的求出所有的连续和(即字串和),还要快速的求出这些连续和的异或值。 小明很快的就求出了所有的连续和,但是小明要考考你,在不告诉连续和的情况下,让你快速求是序列所有连续和的异或值。

输入输出格式

输入格式


第一行输入一个 $n$,表示这序列的数序列 第二行输入 $n$ 个正整数 $a_1,a_2 \dots a_n$ 代表这个序列

输出格式


输出这个序列所有的连续和的异或值

输入输出样例

输入样例 #1

3
1 2 3

输出样例 #1

0

说明

【样例解释】 序列 $1$ $2$ $3$ 有 $6$ 个连续和,它们分别是 $1$ $2$ $3$ $3$ $5$ $6$,则 $1 \text{ xor } 2 \text{ xor } 3 \text{ xor } 3 \text{ xor } 5 \text{ xor } 6 = 0$ 【数据范围】 对于 $20\%$ 的数据,$1\le n \le 100$ 对于 $100\%$ 的数据,$1\le n \le 10^5$,$\sum\limits_{i=1}^na_i \le 10^6$