题目描述

给定一个长度为 $N$ 的正整数数组 $A$。

对于每个形如

的连续子数组，如果端点 $A_i$ 与 $A_j$ 的最大公约数大于 $1$，则计算该子数组的异或值：

再将所有这些得到的子数组异或值继续做异或，最终得到一个数 $B$。

请计算 $B$。

输入格式

第一行包含整数 $N$。

第二行包含 $N$ 个正整数，表示数组 $A$。

输出格式

输出一个整数，表示 $B$。

数据范围

• $1\le N\le 100000$；
• $1\le A_i\le 1000000$。

子任务

样例

5
4 7 6 10 21

1

满足条件的连续子数组为：

(4, 7, 6)
(4, 7, 6, 10)
(7, 6, 10, 21)
(6, 10)
(6, 10, 21)

它们的异或值分别为 $5,15,30,12,25$，再次异或后得到 $B=1$。