A. 子段与子段

题目描述

对于一个序列$a_1,a_2,\dots,a_n$，子段是指它的一个连续部分，即$a_l,a_{l+1},\dots,a_r$

容易发现，一个长度为$n$的序列有$\frac{n(n+1)}{2}$个子段。例如序列$3,7,4$有下列子段：

$(3),(3,7),(3,7,4),(7),(7,4),(4)$

Mia希望分别求出这些子段的异或和，再将它们异或起来。但是Cierra觉得这太简单了，所以她提出了$q$个询问，每次给出一个区间$[L,R]$，希望你将这个下标区间对应的子段截取出来，回答上面的询问。

具体来说，对询问$[L,R]$，你需要回答$a_L,a_{L+1},\dots,a_R$的所有子段异或和的异或和。

第一行包含两个用空格隔开的整数$n,q$

第二行包含$n$个用空格隔开的整数$a_1,a_2,\dots,a_n$

之后$q$行，每行包含两个用空格隔开的整数$L,R$，依次代表$q$组询问

对每个询问输出一行，包含一个整数，为该区间所有子段异或和的异或和

2
6
0

对于30%的数据，$n,q \leq 500$

对于60%的数据，$n,q \leq 5000$

对于100%的数据，$1 \leq n,q \leq 200000,0 \leq a_i \leq 10^9$，每一组$L,R$均满足$1 \leq L \leq R \leq n$

1000ms, 512MB