题目背景

比特歪子叉哦啊

题目描述

有一个长度为 $2^n$ ，下标从 $1$ 开始的的序列 $a$，保证是 $0$ 到 $2^n-1$ 的排列。

定义一个区间的权值为，选择一个 $v$，将这个区间里的数都 xor 上 $v$ 之后，区间内数 $\operatorname{mex}$ 的最大值。其中 $\operatorname{mex}$ 定义为最小的没有出现的自然数。

有 $q$ 个询问，每个询问用一个区间 $[l,r]$ 表示，你需要对于每个询问，求出所有区间 $[x,y]$ 满足 $l\leq x\leq y\leq r$ 的权值和。

输入格式

第一行两个数 $n,q$。

第二行 $2^n$ 个数，表示序列 $a$。

接下来 $q$ 行每行两个数 $l,r$，表示一次询问。

输出格式

对于每个询问，输出权值和。

样例

样例输入 1

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

样例输出 1

9
3
4
19

样例 2,3,4

见下发文件，分别满足测试点 $5\sim 7,10\sim 14,15\sim 17$ 的限制。

提示与说明

对于全部数据，$n\leq 17,q\leq 5\times 10^5$，$a$ 保证为 $0$ 到 $2^n-1$ 的排列。