Description
对于一个序列a_1,a_2,...,a_n，子段是指它的一个连续部分，即a_l,a_{l+1},...,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},...,a_R的所有子段异或和的异或和。
Input
第一行包含两个用空格隔开的整数n,q
第二行包含n个用空格隔开的整数a_1,a_2,...,a_n
之后q行，每行包含两个用空格隔开的整数L,R，依次代表q组询问
Output
对每个询问输出一行，包含一个整数，为该区间所有子段异或和的异或和
5 3
1 2 3 4 5
1 3
2 4
2 5
HINT
对于30%的数据，n,q <= 500
对于60%的数据，n,q <= 5000
对于100%的数据，1 <= n,q <= 200000,0 <= a_i <= 10^9，每一组L,R均满足1 <= L <= R <= n