Pig

原题目名称：内存较小的电脑

题目描述

给你一个长为 $N$ 的非负整数序列 $A$ 和一台内存较小的评测机。有 $Q$ 次询问，每次询问给出两个数 $L,R$，询问 $\displaystyle \sum_{i=l}^r{A_i}$。因为输出规模有限，所以你只需要输出所有询问答案的异或和。

输入格式

第一行两个正整数用空格分隔，分别表示 $N,Q$。

第二行 $N$ 个非负整数表示序列 $A$。

最后 $Q$ 行，每行两个正整数表示 $L,R$。

输出格式

一行一个整数表示所有询问答案的异或和。

输入输出样例 #1

输入 #1

5 5
8 9 0 1 2
3 3
1 5
3 4
1 2
1 3

输出 #1

21

说明/提示

数据范围

本道题采用通信题方式现场生成数据，使用 Testlib 进行随机，保证了数据的一致性并节约了数据存储空间，但是会使得该题的数据强度不足、评测时间较长。对于选手程序，只需使用普通的 stdin/stdout 即可。由于我不知道怎么做，本题暂不支持 Hack。

对于全部测试数据，保证 $1 \le N \le 5 \times 10^5,1 \le Q \le 1.5 \times 10^5,0 \le A_i \le 10^6, 1 \le L \le R \le N$。

题目资源