問題文

長さ $N$ の数列 $a_1, a_2, \dots, a_N$ があります。
$\displaystyle \bigoplus_{i = l}^{r} a_i = a_l\ xor\ a_{l+1}\ xor\ \dots\ xor\ a_r$ とします。
$j(1 \le j \le Q)$ 番目のクエリでは、$\displaystyle \bigoplus_{i = l_j}^{r_j} a_i$ を求めてください。
$a\ xor\ b$ とは、$a, b$ を二進数であらわしたとき、各桁について $a, b$ どちらもビットが立っているまたは立っていないときその桁が $0$、それ以外の時に $1$ となるような演算です。詳しくは「排他的論理和」で検索してください。

入力

$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$

出力

改行区切りで $Q$ 行にわたって答えを出力せよ。最後に改行せよ。

サンプル

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