Time limit: 3 seconds

Memory limit: 1024 megabytes

题目描述

本题分简单和困难两个版本，本题为困难版，除题意外，数据范围和时空限制均有区别。

这里有个长为 $n$ 的 丑陋的 非负整数 序列 $a$。

为什么说他丑陋呢？因为 slc 觉得无论他选择哪个区间，将里面的元素 进行四则运算后 得到的值都很诡异。

庆幸的是，slc 在最近学会了美丽的位运算，只要对于所选区间中的所有元素进行 按位异或运算，得到的结果就是美丽的。

现在，slc 有 $q$ 个询问，每次询问给定两个整数 $l~r$，代表所取区间的左右端点，你能给出 将这个区间内所有元素进行 按位异或运算 后的值吗？

按位异或运算：将两个整数作为二进制数，对二进制表示中的每一位逐一运算。其中 $0 \oplus 0 = 0,0 \oplus 1 = 1,1 \oplus 0 = 1,1 \oplus 1 = 0$。

例：$5 \oplus 6 = (101)_2 \oplus (110)_2 = (011)_2 = 3$。

输入

第一行给定两个整数 $n, q$，为序列的长度和询问的数量。

第二行包含 $n$ 个整数，为序列 $a$ 的长度。

接下来总共包含 $q$ 行，每行包含两个整数 $l~r$，为所取区间的左右端点。

输出

对于每个询问，输出一行一个整数 $x$，为区间内所有元素进行 按位异或运算 后的值。

限制

$1 \leq n \leq 2 \times10 ^ 5$

$1 \leq q \leq 2 \times 10 ^ 5$

$0 \leq a_i \leq 5 \times 10 ^ {9}$

13 5
1 1 4 5 1 4 1 9 1 9 8 1 0
1 6
7 13
1 3
4 6
1 1

4
9
4
0
1

样例解释

对于第四个询问，给定 $4, 6$ 作为左右端点，对应区间内的数为 $5, 1, 4$，$5 \oplus 1 \oplus 4 = 0$，因此答案为 $0$。