eolymp
bolt
Try our new interface for solving problems
Problems

Find XOR on a segment

Find XOR on a segment

Time limit 1 second
Memory limit 128 MiB

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