Description

Arctic_Bake 对位运算很不熟悉，于是找 guanmiantang_h 要一道位运算相关的题。

guanmiantang_h 拿出了一个长度为 $n$ 的数组 $a$。在一次询问中将给出两个整数 $x, y$ $(1 \leq x \leq y \leq n)$，要求所有 $x \leq i \leq y$ 中对任意一个 $i$， $a_i$ 都要参与异或运算，求这些数异或运算在一起的结果。

``这是不是太简单了？'' Arctic_Bake 问。

``你先别急'' guanmiantang_h 说。

这样的询问总共有 $m$ 次，每次会给出两个整数 $x_i, y_i$ $(1 \leq x_i \leq y_i \leq n)$。每次询问后，都需要输出将下标 $x_i$ 和 $y_i$ 之间的所有数异或运算在一起的结果。

Format

Input

第一行有两个整数 $n, m$ $(1 \leq n, m \leq 10^5)$。

第二行有 $n$ 个整数 $a_1, a_2, \cdots, a_n$ $(1 \leq a_i \leq 10^9)$，表示那个数组。

接下来有 $m$ 行，每行有两个整数 $x_i, y_i$ $(1 \leq x_i \leq y_i \leq n)$，表示每次询问进行运算的两个端点。

Output

输出有 $m$ 行。

第 $i$ 行应该输出一个整数，表示第 $i$ 次询问中两段中间所有数异或运算在一起的结果。

Samples

4 3
2 5 9 1000000000
1 4
2 3
1 1

1000000014
12
2

Note

对于 $c = a \bigoplus b$，若 $a$ 和 $b$ 二进制下对应 bit 位不同，则为 $1$，否则为 $0$。在 C 语言中，用 $a$ ^ $b$ 来表示。

比如 $5 \bigoplus 6 = 101_2 \bigoplus 110_2 = 011_2 = 3$。

异或有这样一些性质：

归零律：$a \bigoplus a = 0$;

恒等律：$a \bigoplus 0 = a$;

交换律：$a \bigoplus b = b \bigoplus a$;

结合律：$ a \bigoplus b \bigoplus c = a \bigoplus (b \bigoplus c) = (a \bigoplus b) \bigoplus c$; 自反： $\ \$$a \bigoplus b \bigoplus a = b$;

Limitation

1s, 1024KiB for each test case.