题目描述

给定 $n$ 个正整数组成的序列（$a_1$ 至 $a_n$）。$m$ 次询问，每次询问一个区间$[l_i,r_i]$ 中出现奇数次的数的异或和。

输入格式

第一行两个正整数 $n$ 和 $m$ ；

第二行 $n$ 个正整数组成的序列；

以下 $m$ 行，每行两个数，表示询问的区间 $[l_i,r_i]$。

输出格式

对于每个询问一行，输出结果。

输入输出样例

10 5
4 5 4 8 6 9 5 8 7 4
1 8
2 9
5 10
1 10
5 9

15
12
1
12
5

数据范围

对于 $30\%$ 的得分： $1\le n,m\le4\times10^5$；

对于 $100\%$ 的得分： $1\le n,m\le 5\times10^6$，$1\le a_i\le 2^{31}-1$。