小米什卡喜欢编程。由于她的生日刚刚过去,她的朋友们决定送给她一个非负整数数组 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$$。