The array a is given. Find the value of XOR (bitwise exclusive or) on the segment.
The first line contains the number n (1≤n≤106) of array elements.
The second line contains n integers ai (0≤ai≤109) — the elements of the array a.
The third line contains the number q (1≤q≤106) of XOR requests on the segment.
Each of the following q lines contains two integers li and ri (1≤li≤ri≤n) — the boundaries of the array segment where you must find XOR.
For each query, print in a separate line the XOR of elements on the corresponding segment of array (including borders).