Haitang 定义非负整数序列的 mex 为不属于该数组的最小非负整数。例如，$\text{mex}([0, 1, 3]) = 2$。

Haitang 定义非负整数序列的 xormex 为该序列中的每个元素与同一个非负整数进行异或运算后，所得序列的 mex 的最大值。例如，$\text{xormex}([8, 9, 11]) = \text{mex}([8 \oplus 9, 9 \oplus 9, 11 \oplus 9]) = \text{mex}([1, 0, 2]) = 3$。

给定一个长度为 $2^n$ 的排列 $a$ 和 $m$ 次询问，每次询问包含两个整数 $l_i$ 和 $r_i$，你需要计算对于所有 $l_i \le x \le y \le r_i$，子数组 $[a_x, a_{x+1}, \dots, a_y]$ 的 xormex 之和。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 18, 1 \le m \le 10^6$)，表示排列的大小和询问次数。

第二行包含 $2^n$ 个整数 $a_i$ ($0 \le a_i < 2^n$)，表示排列 $a$。

接下来的 $m$ 行，每行包含两个整数 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le 2^n$)，表示该次询问的区间 $[l_i, r_i]$。

输出格式

输出 $m$ 行，每行包含一个整数，表示第 $i$ 次询问的答案。

样例

样例输入 1

2 4
3 2 0 1
1 3
2 3
1 2
1 4

样例输出 1

9
3
4
19

样例输入 2

3 5
0 4 6 7 5 2 1 3
1 8
3 5
2 6
3 7
1 4

样例输出 2

93
9
29
22
15