题目描述

给你一个长度为 $n$ 的数组 $a_1,a_2,...,a_n$。
给你 $q$ 次询问，每次询问给你两个参数 $l,r$，问你 $a_l \space xor \space a_{l+1}\space xor\space ...\space xor\space a_r$ 的值为多少？

输入格式

第一行两个整数 $n,q$。
第二行 $n$ 个整数，表示 $a_1,a_2,...,a_n$。
接下来 $q$ 行，每行两个整数 $l,r$，表示对应的询问。

输出格式

输出 $q$ 行，表示每个询问的答案。

输入输出样例 #1

输入 #1

6 3
3 2 1 10 9 4
1 2
2 5
3 6

输出 #1

1
0
6

说明/提示

$1\le n,q\le 10^6,1\le a_i\le 10^9$。