由于疯狂地使用球拍拍打苍蝇，Marin 遭受了严重的身体损伤，医学界称之为肱骨外上髁炎（俗称网球肘）。他的祖母建议他在伤处涂抹拉基亚酒（rakija），医生给他开了一种强效止痛药，但 Marin 忽略了所有的建议，决定在整数序列中寻找答案。

他发现了一个以前未被发现的整数序列，并将其命名为 xorbonacci 序列。序列中的第 $n$ 个元素记为 $x_n$。该序列以如下递归方式定义：

$$x_1 = a_1$$ $$x_2 = a_2$$ $$\dots$$ $$x_k = a_k$$ $$x_n = x_{n-1} \oplus x_{n-2} \oplus \dots \oplus x_{n-k}, \quad n > k$$

出于只有 Marin 自己知道的原因，他认定如果能回答由数字 $l$ 和 $r$ 定义的 $Q$ 个询问，他的所有痛苦都会消失。询问的答案由以下值表示：

$$x_l \oplus x_{l+1} \oplus \dots \oplus x_{r-1} \oplus x_r$$

请帮助 Marin 并回答他的询问。

注意：运算符 $\oplus$ 表示按位异或（binary XOR）运算。

输入格式

第一行包含一个整数 $K$（$1 \le K \le 100\,000$）。

第二行包含 $K$ 个整数，表示 xorbonacci 序列的前 $K$ 个元素。所有数字均小于 $10^{18}$。

第三行包含一个整数 $Q$（$1 \le Q \le 10^6$）。

接下来的 $Q$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le 10^{18}$），表示 Marin 的第 $i$ 个询问。

输出格式

输出共 $Q$ 行，每行包含一个整数，表示对 Marin 询问的回答，顺序与输入一致。

样例

输入样例 1

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

输出样例 1

3
1
0

输入样例 2

5
3 3 4 3 2
4
1 2
1 3
5 6
7 9

输出样例 2

0
4
7
4