题目描述

小 Z 有一个长度为 $n$ 的正整数序列 $A = \{a_1, a_2, \cdots, a_n\}$，序列下标为 $[0, n-1]$。现有一个二维数组 $b$，执行以下函数：

void init(){
    for(int i=0;i<n;i++) b[0][i]=a[i];
    for(int i=1;i<n;i++)
        for(int j=0;j<n-i;j++) b[i][j]=b[i-1][j]^b[i-1][j+1];
}

现给出 $q$ 次询问，每次询问给定非负整数 $x, y$，保证有 $0 \le x + y \le n - 1$，请输出 $b[x][y]$ 的权值大小。

输入格式

第一行包含 $2$ 个正整数 $n, q$。

第二行给定长度为 $n$ 的正整数数列 $a$。

之后 $q$ 行，每行给出 $2$ 个参数 $x, y$，表示一次询问。

输出格式

输出 $q$ 行，每行输出 $1$ 个整数，表示最终答案。

样例

输入数据 1

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

输出数据 1

11
9
9
7

输入数据 2

此样例保证每组询问的 $x, y$ 为所有可能的询问中等概率生成的。

点此链接 ex_xor2.in 和 ex_xor2.ans 下载大样例 2 输入和输出数据。

说明/提示

样例 1 解释

$b$ 序列的形态为：

9 5 9 2
12 12 11
 0 7
 7

对于每次询问：

• $b[1][2] = 9 \oplus 2 = 11$
• $b[0][0] = 9$
• $b[0][2] = 9$
• $b[3][0] = 9 \oplus 5 \oplus 9 \oplus 2 = 7$

数据范围

对于 $20\%$ 的数据，$1 \le n \le 5000$。

对于 $40\%$ 的数据，数据保证每组询问的 $x, y$ 为所有可能的询问中等概率生成的。

对于所有测试数据，$1 \le n, q \le 10^5$，$0 \le a_i \le 10^9$。