Problem Description

给定大小为 $n$ 的数组 $a_0,...,a_{n-1}$。

构造 $b$ 数组，$\forall 0 \leq x < n$ 有 $b_{0,x} = a_x$, 并对于 $\forall x>0,x+y \leq n-1$，有 $b_{x, y} = b_{x-1,y} \oplus b_{x-1,y+1}$ ，其中 $\oplus$ 表示异或操作。

有 $q$ 次询问，询问每次给出 $(x, y)$，请你输出 $b_{x, y}$ 的值。

Input

第一行包含一个正整数表示 $n$。

第二行给出 $n$ 个数字 $a_0, ..., a_{n-1}$。

第三行包含一个正整数表示 $q$。

之后 $q$ 行，每行给定 $2$ 个整数，给出 $x,y$ 表示一组询问，满足 $0 \leq x+y < n$。


#### 评测数据规模：

对于所有测评数据，$n,q \leq 3 \times 10^5, a_i \leq 10^9$。

Output

输出 $q$ 行，表示 $q$ 次询问的答案。

### 样例解释

以下给出 $b$ 的具体数值。

```text
9 5 9 2
12 12 11
0 7
7
```

4
9 5 9 2
4
1 2
0 0
0 2
3 0

11
9
9
7