Xiao Ming from Jiali Middle School loves math competitions. Many problems in math competitions are related to the contiguous subsequences of a sequence. Therefore, for a given sequence, finding the sum of all its contiguous subsequences is very simple for Xiao Ming. However, today Xiao Ming encountered a difficult sequence problem. This problem not only requires you to quickly find the sum of all contiguous subsequences but also to quickly find the XOR sum of all contiguous subsequences. Xiao Ming can quickly find the sum of all contiguous subsequences, but he wants to test you: without telling you the contiguous subsequences, can you quickly find the XOR sum of all contiguous subsequences of the sequence?

Input

The first line contains an integer $n$, representing the number of elements in the sequence. The second line contains $n$ integers $a_1, a_2, a_3, \dots, a_n$, representing the sequence. $0 \le a_1, a_2, \dots, a_n$, $0 \le a_1 + a_2 + \dots + a_n \le 10^6$.

Output

Output the XOR sum of all contiguous subsequences of this sequence.

Examples

Input 1

3
1 2 3

Output 1

0

Note

The sequence $1, 2, 3$ has $6$ contiguous subsequences, which are $1, 2, 3, 1+2=3, 2+3=5, 1+2+3=6$. Then $1 \oplus 2 \oplus 3 \oplus 3 \oplus 5 \oplus 6 = 0$.

Constraints

For $20\%$ of the data, $1 \le n \le 1000$. For $100\%$ of the data, $1 \le n \le 10^5$.