Magic Formulas

2000ms

262144K

Description:

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₁, p₂, ..., p_n. Lets write down some magic formulas:

$\text{[math]}$ $\text{[math]}$

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

The expression $\text{[math]}$ 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.

Input:

The first line of the input contains the only integer n (1 ≤ n ≤ 10⁶). The next line contains n integers: p₁, p₂, ..., p_n (0 ≤ p_i ≤ 2·10⁹).

Output:

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

Sample Input:

3
1 2 3

Sample Output:

Informação

Provedor Codeforces

Código CF424C