Problems
Find XOR on a segment
Find XOR on a segment
The array a is given. Find the value of XOR (bitwise exclusive or) on the segment.
Input data
The first line contains the number n~(1 \le n \le 10^6) of array elements.
The second line contains n integers a_i~(0 \le a_i \le 10^9) — the elements of the array a.
The third line contains the number q~(1 \le q \le 10^6) of XOR requests on the segment.
Each of the following q lines contains two integers l_i and r_i~(1 \le l_i \le r_i \le n) — the boundaries of the array segment where you must find XOR.
Output data
For each query, print in a separate line the XOR of elements on the corresponding segment of array (including borders).
Examples
Input example #1
5 1 2 3 4 5 5 1 5 2 4 3 5 1 3 3 4
Output example #1
1 5 2 0 7