CF703D Mishka and Interesting sum

小米什卡喜欢编程。由于她的生日刚刚过去，她的朋友们决定送给她一个由 $n$ 个元素组成的非负整数数组 $a_{1},a_{2},...,a_{n}$！ 米什卡非常喜欢这个数组，并立刻决定要计算它的美丽值，但她太小了，无法处理大型数组。因此，她邀请你来帮忙，并请你处理 $m$ 个查询。 每个查询的处理方式如下： 1. 指定两个整数 $l$ 和 $r$（$1\leq l\leq r\leq n$），表示查询区间的左右边界。 2. 把区间 $[l,r]$（即序列 $a_{l},a_{l+1},...,a_{r}$）中出现次数为偶数次的整数写下来。 3. 计算这些写下来的整数的异或和，作为本次查询的答案。形式化地说，若写下来的整数为 $x_{1},x_{2},...,x_{k}$，则米什卡想要知道 $\displaystyle x_{1}\oplus x_{2}\oplus\dots\oplus x_{k}$ 的值，这里 $\oplus$ 表示按位异或运算。 由于只有小熊们知道数组美丽值的定义，你只需按照要求依次输出每个查询的答案即可。

输入的第一行包含一个整数 $n$（$1 \leq n \leq 1000000$），表示数组的元素个数。 第二行包含 $n$ 个整数 $a_{1},a_{2},...,a_{n}$（$1 \leq a_{i} \leq 10^{9}$），表示数组中的元素。 第三行包含一个整数 $m$（$1 \leq m \leq 1000000$），表示查询的个数。 接下来的 $m$ 行中，每行包含两个整数 $l$ 和 $r$（$1 \leq l \leq r \leq n$），表示每个查询的区间范围。

输出 $m$ 个非负整数，依次表示每个查询的答案，每行一个。

在第二个样例中： 第一个查询区间中，没有任何数出现了偶数次，所以答案是 $0$。 第二个查询区间中，只有整数 $3$ 出现了偶数次，所以答案是 $3$。 第三个查询中，只有整数 $1$ 被写下来，答案是 $1$。 第四个查询中，考虑全部数组元素，只有 $1$ 和 $2$ 是出现偶数次的，答案是 $1 \oplus 2 = 3$。 第五个查询中，$1$ 和 $3$ 被写下来，答案是 $1 \oplus 3 = 2$。 由 ChatGPT 5 翻译