Poi 的新加法（Hard Version）
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

\hspace{15pt}本题为问题的困难版本，两题的唯一区别在于询问的次数及询问的数据范围。

\hspace{15pt}Poi 发明了一种新的加法：二进制只进位加法（下文用 f(x,y) 指代）。在这种加法下（为了便于理解，本表中数字使用二进制表达）：
$x$ $y$ $f(x,y)$
$\texttt{00}$ $\texttt{00}$ $\texttt{00}$
$\texttt{00}$ $\texttt{01}$ $\texttt{00}$
$\texttt{01}$ $\texttt{00}$ $\texttt{00}$
$\texttt{01}$ $\texttt{01}$ $\texttt{10}$

\hspace{15pt}需要注意的是，我们只考虑一次进位，即不考虑进位造成的其他位的变动导致的再次进位，比如 f(\texttt{11},\texttt{01})=\texttt{10}。
\hspace{15pt}简而言之，f(x,y)=x+y -(x \oplus y)，其中 \oplus 代表二进制按位异或运算。
\hspace{15pt}现在，给定一个长度为 n 的序列 \{a_1, a_2, \dots, a_n\}。你需要处理 q 个查询，每个查询会给定 l 和 r，求解：

f\Bigg(<br /> f\bigg(<br /> f\Big(<br /> \cdots <br /> f\big(<br /> f(a_l , a_{l+1}) , <br /> a_{l+2}<br /> \big), <br /> \cdots<br /> \Big) , <br /> a_{r-1}<br /> \bigg) , a_r<br />\Bigg)

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leq T\leq 10^6\right) 代表数据组数，每组测试数据描述如下：
\hspace{15pt}第一行输入两个整数 n, q \left(1\leq n, q \leq 10^6\right)，代表序列中的元素个数、查询次数。 
\hspace{15pt}第二行输入 n 个整数 a_1, a_2, \dots, a_n \left(0 \le a_i \lt 2^{60}\right)，代表序列中的元素。 
\hspace{15pt}此后 q 行，第 i 行输入两个整数 l_i, r_i \left(1 \le l_i \le r_i \le n\right)，代表第 i 次询问的区间。

\hspace{15pt}除此之外，保证单个测试文件的 n 之和不超过 10^6，q 之和不超过 10^6。

输出描述:

\hspace{15pt}对于每个查询，新起一行。输出一个整数，代表该次查询的结果。
示例1

输入

复制 
3
3 3
2 3 3
1 1
1 2
1 3
8 3
0 13 0 0 0 7 2 1
2 2
6 7
1 8
5 5
31 31 31 31 31
1 1
1 2
1 3
1 4
1 5

输出

复制 
2
4
0
13
4
0
31
62
60
56
48

备注: