问题描述

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$。

你需要处理 $m$ 次询问。每次询问给定两个整数 $l,r$，请输出区间 $[l,r]$ 内所有数的按位异或结果，即：

其中 $\oplus$ 表示按位异或运算。

输入格式

第一行包含两个整数 $n,m$。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$。

接下来 $m$ 行，每行包含两个整数 $l,r$，表示一次询问。

输出格式

对于每次询问，输出一行一个整数，表示区间 $[l,r]$ 的异或和。

样例输入

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

样例输出

0
0
3

说明

定义前缀异或和数组：

则区间 $[l,r]$ 的异或和可以表示为：

其中约定 $s_0 = 0$。

通过预处理前缀异或和，可以在 $O(1)$ 时间内回答每次询问。

评测数据规模

对于所有数据：

$1 \le n,m \le 2 \times 10^5$

$0 \le a_i \le 2^{20}$

$1 \le l \le r \le n$