Problem Statement

There is a sequence $a_1, a_2, \dots, a_N$ of length $N$.
Let $\displaystyle \bigoplus_{i = l}^{r} a_i = a_l\ xor\ a_{l+1}\ xor\ \dots\ xor\ a_r$.
For the $j(1 \le j \le Q)$-th query, find $\displaystyle \bigoplus_{i = l_j}^{r_j} a_i$.
$a\ xor\ b$ is the operation such that, when $a, b$ are written in binary, each digit is $0$ if the bit is set in both $a, b$ or in neither of them, and $1$ otherwise. For details, search for "exclusive or".

Input

$N\ Q$
$a_1\ a_2\ \dots\ a_N$
$l_1\ r_1$
$l_2\ r_2$
$\dots$
$l_Q\ r_Q$

$1 \le N, Q \le 2 \times 10^5$
$1 \le a_i \le 10^5$
$1 \le l_j \le r_j \le N$

Output

Output the answers over $Q$ lines, separated by newlines. Print a newline at the end.

Sample

10 10
4 1 3 10 1 4 9 4 2 7
1 10
10 10
1 5
1 5
2 4
4 10
1 2
1 4
9 9
5 10

1
7
13
13
8
7
5
12
2
13