[功不唐捐-2013]_强哥的无敌异或

Time Limit: 3000 ms Memory Limit: 65536 KiB

Problem Description

强哥是一个热爱学习的人,他经常去维基百科学习计算机科学。

他在学习位运算时发现了异或的秘密。

就在刚才,强哥认真地学习了一系列位运算符 ,其中按位异或的运算符 xor 对他影响很大。按位异或的运算符是双目运算符。按位异或具有交换律,即i xor j = j xor i。

他发现,按位异或可以理解成被运算的数字的二进制位对应位如果相同,则结果的该位置为0,否则为1,例如1(01) xor 2(10) = 3(11)。

他还发现,按位异或可以理解成数字的每个二进制位进行了不进位的加法,例如3(11) xor 3(11) = 0(00)。

 

现在强哥给你一个长度为n的数列 , 然后给出q次询问[l , r] , 每次询问请你输出 [l, r] 之间出现次数为奇数次的数字的异或和 。

注: 异或即按位异或, C语言运算符号为 ^ ;  

Input

给出T组数据 。
每组先给出一个 n 。
然后给出 n 个数字 , 每个数字小于等于 100000 ;
然后给出 q , 接下来 q 行, 每行一个 l , r 。

(n <= 100000,T <= 5,q <= 100000,1 <= l <= r <= n )

 

Output

对于每个输入,输出一行,包含一个整数,即为每次询问的答案。

Sample Input

1
3
1 2 3
2
1 3
2 3

Sample Output

0
1

Hint

Source

【重聚--SDUTACM十周年庆典专场赛】Ransln