A9381 | Magic Formulas

People in the Tomskaya region like magic formulas very much. You can see some of them below.

Imagine you are given a sequence of positive integer numbers $p_{1}$ , $p_{2}$ , ..., $p_{n}$ . Lets write down some magic formulas:

Here, "mod" means the operation of taking the residue after dividing.

The expression  means applying the bitwise $xor$ (excluding "OR") operation to integers $x$ and $y$ . The given operation exists in all modern programming languages. For example, in languages C++ and Java it is represented by "^", in Pascal — by "xor".

People in the Tomskaya region like magic formulas very much, but they don't like to calculate them! Therefore you are given the sequence $p$ , calculate the value of $Q$ .

The first line of the input contains the only integer $n$ ( $1<=n<=10^{6}$ ). The next line contains $n$ integers: $p_{1},p_{2},...,p_{n}$ ( $0<=p_{i}<=2·10^{9}$ ).

The only line of output should contain a single integer — the value of $Q$ .