异或查询 - ROJ

初始时给定一个长度为 $n$ 的正整数序列 $a_i$ ，序列下标为 $[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 \leq x+y \leq n-1$ ，试给出 $b[x][y]$ 的权值大小。

提示：组合数 $C_a^b \bmod 2=[a & b = b]$

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

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

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

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

$b$ 序列的形态为

见下发文件，数据保证每组询问的 $x,y$ 为所有可能的询问中等概率生成的。

见下发文件。

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

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

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

下发数据