Find XOR on a segment

Very easy

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

The array $a$ is given. Find the value of XOR (bitwise exclusive or) on the segment.

Input

The first line contains the number $n (1 \leq n \leq 1 0^{6})$ of array elements.

The second line contains $n$ integers $a_{i} (0 \leq a_{i} \leq 1 0^{9})$ — the elements of the array $a$ .

The third line contains the number $q (1 \leq q \leq 1 0^{6})$ of XOR requests on the segment.

Each of the following $q$ lines contains two integers $l_{i}$ and $r_{i} (1 \leq l_{i} \leq r_{i} \leq n)$ — the boundaries of the array segment where you must find XOR.

Output

For each query, print in a separate line the XOR of elements on the corresponding segment of array (including borders).

Examples

Input #1

Answer #1

Submissions 317

Acceptance rate 32%