XOR of All Contiguous Subarray Sums

Given a sequence of integers, define the contiguous subarray sum as \(S(i,j)=\sum_{k=i}^{j} a_{k}\) for all \(1 \le i \le j \le n\). The task is to compute the XOR of all these contiguous subarray sums without explicitly listing them.

For example, if the sequence is [1, 2, 3], then its contiguous subarray sums are: 1, 3, 6, 2, 5, and 3. The XOR of these values is \(1 \oplus 3 \oplus 6 \oplus 2 \oplus 5 \oplus 3 = 0\) (where \(\oplus\) denotes the bitwise XOR operation).

inputFormat

The first line contains an integer (n), denoting the number of elements in the sequence. The second line contains (n) space-separated integers representing the sequence.

outputFormat

Output a single integer, which is the XOR of all contiguous subarray sums.

sample

3
1 2 3

0