A13318 | 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

$$$$ (a_1 + a_2) \oplus (a_1 + a_3) \oplus \ldots \oplus (a_1 + a_n) \\ \oplus (a_2 + a_3) \oplus \ldots \oplus (a_2 + a_n) \\ \ldots \\ \oplus (a_{n-1} + a_n) \\ $$ </p><p>Here $x \\oplus y$ is a bitwise XOR operation (i.e. $x$ <span class="tex-font-style-tt">^</span> $y$$$ in many modern programming languages). You can read about it in Wikipedia: [https://en.wikipedia.org/wiki/Exclusive\_or#Bitwise\_operation](https://en.wikipedia.org/wiki/Exclusive_or#Bitwise_operation).

The first line contains a single integer $n$ ( $2 \leq n \leq 400\,000$ ) — the number of integers in the array.

The second line contains integers $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq 10^7$ ).

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