Find XOR on a segment

Input

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

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

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

Each of the following $q$ lines contains two integers $l_{i}$ l_i and $r_{i} (1 \leq l_{i} \leq r_{i} \leq n)$ r_i~(1 \le l_i \le r_i \le 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

Example 1

Loading