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