33463번 - Xor 서브태스크다국어

문제

Fran recently learned the operation xor, which for two integers $x$ and $y$ returns the result by applying the bitwise exclusive or (exclusive or). The operation xor, denoted as $\oplus,ドル compares the corresponding bits of the numbers $x$ and $y$ and sets the result bit at each position according to the following rule:

• If the bits at the corresponding position are different (0ドル$ and 1ドル,ドル or 1ドル$ and 0ドル$), then the result bit is 1ドル$.
• If the bits are the same (0ドル$ and 0ドル,ドル or 1ドル$ and 1ドル$), then the result bit is 0ドル$.

For example, for $x = 5$ and $y = 3,ドル the binary representations are: $x = 101_2,ドル $y = 011_2$. Applying xor to the corresponding bits gives $x \oplus y = 101_2 \oplus 011_2 = 110_2 = 6$. In other words, 5ドル \oplus 3 = 6$.

Fran received an array of $n$ integers $a_1, a_2, \dots , a_n$ and decided to do the following:

1. For every pair of indices $(i, j)$ where 1ドル ≤ i ≤ j ≤ n,ドル he calculated the sum $a_i + a_j$.
2. Now he wants to calculate the result of the xor of all the obtained sums.

Help Fran calculate the required result.

입력

In the first line of input, there is $n$ (1ドル ≤ n ≤ 5 \cdot 10^5$), the length of the array.

In the second line, there are $n$ numbers $a_1, a_2, \dots , a_n$ (0ドル ≤ a_i < 2^{30}$) as described in the problem statement.

출력

In the only line of output, print the required result.

제한

서브태스크

노트

Clarification of the first example:

The sums are 2ドル + 2 = 4,ドル 2ドル + 4 = 6,ドル 2ドル + 5 = 7,ドル 4ドル + 4 = 8,ドル 4ドル + 5 = 9,ドル and 5ドル + 5 = 10$. The result is 4ドル \oplus 6 \oplus 7 \oplus 8 \oplus 9 \oplus 10 = 14$.