Description

有一个长为n的自然数序列Ai。

有m次询问，每次询问区间[l,r]中出现次数为偶

数的数的异或和。

Format

Input

第一行一个整数n。

第二行一共n个整数表示序列Ai。

第三行一个整数q。

接下来共q行，每行2个整数l,r，表示询问的区间。

N,M<=3*10^5

Ai<2^32

Output

共q行，每行一个整数ans表示答案。

（如果不存在出现偶数次的数，那么答案就是0）

Samples

5 
1 1 5 5 1 
4 
2 5 
5 5
1 4
1 5

4
0
4
5