题目描述

给定一个长度为 $N$ 的整数数组 $\,A[1..N]$。现有 $Q$ 次查询，每次查询给定区间 $[L,R]$，请输出此区间内所有元素的按位异或结果

$A_L \oplus A_{L+1} \oplus \cdots \oplus A_R.$

要求整体时间复杂度 $O(N+Q)$。

输入格式

N Q
A_1 A_2 … A_N
L_1 R_1
…
L_Q R_Q

• 第一行两个整数 $N, Q$（$1 \le N,Q \le 10^6$）。
• 第二行 $N$ 个整数，表示数组 $A$ 的各个元素（$|A_i|\le10^9$）。
• 接下来 $Q$ 行，每行两个整数 $L,R$（$1\le L\le R\le N$），表示一次查询区间。

输出格式

输出 $Q$ 行，每行一个整数，为对应查询的异或结果。

样例

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

1
5
3

数据范围

| 测试点编号 | $N,Q$ 上界 | $|A_i|$ 上界 | |:----------:|:------------:|:--------------:| | 1～2 | $10^5$ | $10^9$ | | 3～5 | $5\times10^5$ | $10^9$ | | 6～10 | $10^6$ | $10^9$ |