Present

문제

Catherine received an array of integers as a gift for March 8. Eventually she grew bored with it, and she started calculated various useless characteristics for it. She succeeded to do it for each one she came up with. But when she came up with another one --- xor of all pairwise sums of elements in the array, she realized that she couldn't compute it for a very large array, thus she asked for your help. Can you do it? Formally, you need to compute

$$\begin{array}{r}{\displaystyle (a_1+a_2)\oplus (a_1+a_3)\oplus \dots \oplus (a_1+a_n)\oplus }\\ {\displaystyle \oplus (a_2+a_3)\oplus \dots \oplus (a_2+a_n)\oplus }\\ {\displaystyle \dots }\\ {\displaystyle \oplus (a_{n-1}+a_n)}\end{array}\backslash begin\{align*\}\; (a\_1\; +\; a\_2)\; \backslash oplus\; (a\_1\; +\; a\_3)\; \backslash oplus\; \backslash ldots\; \backslash oplus\; (a\_1\; +\; a\_n)\; \backslash oplus\; \backslash \backslash \; \backslash oplus\; (a\_2\; +\; a\_3)\; \backslash oplus\; \backslash ldots\; \backslash oplus\; (a\_2\; +\; a\_n)\; \backslash oplus\; \backslash \backslash \; \backslash ldots\; \backslash \backslash \; \backslash oplus\; (a\_\{n-1\}\; +\; a\_n)\; \backslash \backslash \; \backslash end\{align*\}$$

입력

The first line contains a single integer $nn$ ($2\le n\le 4000002\; \backslash leq\; n\; \backslash leq\; 400\backslash ,000$) --- the number of integers in the array.

The second line contains integers $a_1,a_2,\dots ,a_{n}a\_1,\; a\_2,\; \backslash ldots,\; a\_n$ ($1\le a_i\le {10}^{7}1\; \backslash leq\; a\_i\; \backslash leq\; 10^7$).

출력

Print a single integer --- xor of all pairwise sums of integers in the given array.

힌트

In the first sample case there is only one sum $1+2=31\; +\; 2\; =\; 3$.

In the second sample case there are three sums: $1+2=31\; +\; 2\; =\; 3$, $1+3=41\; +\; 3\; =\; 4$, $2+3=52\; +\; 3\; =\; 5$. In binary they are represented as ${011}_2\oplus {100}_2\oplus {101}_2={010}_{2}011\_2\; \backslash oplus\; 100\_2\; \backslash oplus\; 101\_2\; =\; 010\_2$, thus the answer is 2.

$\oplus \backslash oplus$ is the bitwise xor operation. To define $x\oplus yx\; \backslash oplus\; y$, consider binary representations of integers $xx$ and $yy$. We put the $ii$-th bit of the result to be 1 when exactly one of the $ii$-th bits of $xx$ and $yy$ is 1. Otherwise, the $ii$-th bit of the result is put to be 0. For example, ${0101}_2\oplus {0011}_2={0110}_{2}0101\_2\; \backslash ,\; \backslash oplus\; \backslash ,\; 0011\_2\; =\; 0110\_2$.

2
1 2

3

3
1 2 3

2