题目描述

给定序列 $\{a_n\}$，有 $q$ 次询问，每次询问一个区间 $[l,r]$，请你求出对于一个 $r-l+1$ 个点的无向完全图，点的编号为 $l\sim r$，点 $u,v$ 之间的边的边权为 $\text{highbit}(a_u \oplus a_v)$，其最小生成树的边权之和为多少。

其中 $\oplus$ 为按位异或操作，$\text{highbit}(x)$ 表示 $x$ 的二进制最高位，值为 $2^k$，满足 $2^k\le x< 2^{k+1}$。特别的，$\text{highbit}(0)=0$。

输入格式

第一行两个正整数 $n,q$，表示序列长度与询问次数。

第二行 $n$ 个正整数 $a_i$，表示序列 $\{a_n\}$。

接下来 $q$ 行，每行两个正整数 $l,r$，表示询问区间 $[l,r]$。

输出格式

共 $q$ 行，每行一个整数，第 $i$ 行表示第 $i$ 次询问的答案。

样例 1 输入

5 3
7 2 6 1 3
1 5
2 3
3 5

样例 1 输出

8
4
6

样例 2

见选手目录下的 $\boldsymbol{spanning/spanning2.in}$ 与 $\boldsymbol{spanning/spanning2.ans}$。

该样例满足子任务 $1$ 的限制。

样例 3

见选手目录下的 $\boldsymbol{spanning/spanning3.in}$ 与 $\boldsymbol{spanning/spanning3.ans}$。

该样例满足子任务 $5$ 的限制。

样例 4

见选手目录下的 $\boldsymbol{spanning/spanning4.in}$ 与 $\boldsymbol{spanning/spanning4.ans}$。

该样例满足子任务 $6$ 的限制。

数据范围

对于所有测试数据，保证：

• $1\le n,q\le2\times10^5$；
• $0\le a_i< 2^{30}$；
• $1\le l\le r\le n$。

特殊性质 A：保证 $q=1$。

特殊性质 B：保证 $a_i < 128$。