← 返回题目列表

Codeforces · 703/D

D. Mishka 和有趣的总和

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

小米什卡喜欢编程。由于她的生日刚刚过去,她的朋友们决定送给她一个非负整数数组 a1, a2, ..., an,共 n 个元素!

米什卡很喜欢这个阵法,她立即决定确定它的美丽值,但她太小了,无法处理大型阵法。正因为如此,她邀请您拜访她并请您处理我的疑问。

每个查询都按以下方式处理:

1. 指定两个整数 l 和 r (1 ≤ l ≤ r ≤ n) — 查询段的边界。
2. 记录在数组段 [l,  r] 中出现偶数次的整数(按照整数 al, al + 1, ..., ar 的顺序)。
3. 计算写下的整数的异或和,该值是查询的答案。形式上,如果第 2 点中写下的整数为 x1, x2, ..., xk,则 Mishka 想要知道值 $$x_{1} \oplus x_{2} \oplus \ldots \oplus x_{k-1}$$,其中 $$\bigcirc$$ — 异或运算符。

因为只有小熊知道数组美的定义,所以你所要做的就是回答提出的每个问题。

输入

输入的第一行包含单个整数 n (1 ≤ n ≤ 1 000 000) — 数组中的元素数量。

输入的第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109) - 数组元素。

输入的第三行包含单个整数 m (1 ≤ m ≤ 1 000 000) — 查询数。

接下来的 m 行中的每一行都通过一对整数 l 和 r (1 ≤ l ≤ r ≤ n) 描述相应的查询 - 查询段的边界。

输出

打印 m 个非负整数 - 按照查询在输入中出现的顺序排列答案。

示例

输入 #1

3
3 7 8
1
1 3

输出 #1

0

输入 #2

7
1 2 1 3 3 2 3
5
4 7
4 5
1 3
1 7
1 5

输出 #2

0
3
1
3
2

注意

在第二个示例中:

第一个查询的段中没有整数,在段中出现偶数次 - 答案为 0。

在第二个查询中,只有整数 3 出现了偶数次——答案是 3。

在第三个查询中,仅写下整数 1 — 答案为 1。

在第四个查询中,考虑所有数组元素。只有 1 和 2 出现了偶数次。答案是$$1 \oplus 2 = 3$$。

在第五个查询中,写下 1 和 3。答案是$$1 \oplus 3 = 2$$。