← 返回题目列表

Codeforces · 424/C

C. 魔法公式

中文机器翻译题面 查看原题

托木斯卡亚地区的人们非常喜欢魔法公式。您可以在下面看到其中的一些。

假设给你一个正整数序列 p1, p2, ..., pn。让我们写下一些神奇的公式:

$$q_{i} = p_{i} \oplus (i \bmod 1) \oplus (i \bmod 2) \oplus \cdots \oplus (i \bmod n)$$

$$Q = q_{1} \oplus q_{2} \oplus \ldots \oplus q_{n-1}$$

这里,“mod”是指取除法后的余数的操作。

表达式 $$x \oplus y$$ 表示对整数 x 和 y 进行按位异或(不包括“OR”)运算。给定的操作存在于所有现代编程语言中。例如,在 C++ 和 Java 语言中,它用“^”表示,在 Pascal 中用“xor”表示。

托姆斯卡亚地区的人们非常喜欢魔法公式,但他们不喜欢计算它们!因此,给定序列 p,计算 Q 的值。

输入

输入的第一行包含唯一的整数 n (1 ≤ n ≤ 106)。下一行包含 n 个整数:p1, p2, ..., pn (0 ≤ pi ≤ 2·109)。

输出

输出的唯一一行应包含一个整数 - Q 的值。

示例

输入 #1

3
1 2 3

输出 #1

3