托木斯卡亚地区的人们非常喜欢魔法公式。您可以在下面看到其中的一些。
假设给你一个正整数序列 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