jhljx学位运算

Problem Description

jhljx在C++程序设计课程中学习了位运算这个高端的知识，现在他开始上算法课，决定活学活用。。

位运算中异或是一个比较神奇的操作，有0^1=1,1^0=1,0^0=0,1^1=0。

于是jhljx给你了一个长度为n的数组，让你求出该数组的某个子数组（数组中下标连续的一些元素组成的数组）的异或值之和。

Input

输入多组数据。
对于每组数据，第一个行为数据组数n（1<=n<=1000000）
第二行为n个数组元素（保证元素在int范围内）
第三行为一个正整数k（1<=k<=100），表示有k次询问。
接下来为k行，每行为两个数字i和j（1<=i,j<=n），表示子数组的边界。

Output

对于每组数据，输出每次询问的子数组的元素异或值之和。

Sample Input

4
1 2 3 4
3
1 2
2 4
1 4

Sample Output

3
5
4

Hint

• 异或的性质：a^a=0,a^b=c,a^c=b。
• 数据量较大，请用scanf和printf来实现。

Trick

为了防止大家WA到停不下来，这里给出提示，询问时的i和j大小顺序不确定。

Source

改编自小米2017校园招聘笔试，改动较大，已降低难度。

Tutorial

本题帮助大家复习了sum和xor的用法。
如果你轻松地解决了本题，可以思考如何求解一个数组中所有子数组异或和中最大的那个？ 提示：trie
小米2017校招笔试原题：求解一个数组中满足两个数异或值大于m的个数。n~100000
求解算法:贪心+trie/map，复杂度O(nlg(100000))