CF424C.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.

托木斯克地区的人们非常喜欢魔法公式。您可以在下方看到一些示例。

假设给定一个正整数序列 $p_1, p_2, \dots, p_n$。我们写下如下魔法公式：

其中，“mod”表示取模运算（即除法后的余数）。

表达式 表示对整数 $x$ 和 $y$ 执行按位异或（exclusive OR）运算。该运算在所有现代编程语言中均存在：例如，在 C++ 和 Java 中用 “^” 表示，在 Pascal 中用 “xor” 表示。

托木斯克地区的人们虽然非常喜欢魔法公式，但却不喜欢手动计算！因此，现给您提供序列 $p$，请您计算 $Q$ 的值。

The first line of the input contains the only integer n (1 ≤ n ≤ 106). The next line contains n integers: _p_1, _p_2, ..., p__n (0 ≤ p__i ≤ 2·109).

输入的第一行包含唯一一个整数 $n$（$1 \leq n \leq 10^6$）。下一行包含 $n$ 个整数：$p_1,\,p_2,\,...,\,p_n$（$0 \leq p_i \leq 2\cdot10^9$）。

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

输出仅有一行，包含一个整数——即 Q 的值。