给定一个长为 $n$（$1\le n\le 6\times 10^5$）的非负整数序列 $a_0,a_1,\dots,a_{n-1}$（$0\le a_i < 2^{30}$）。
有 $q$ 个询问（$1\le q\le 10^6$）。
每次询问给出两个整数 $l,r$（$0\le l\le r < n$），求有多少对整数 $(x,y)$ 满足：
- $l\le x\le y\le r$；
- $\forall i,j\in S\ :i\oplus j\in S$，其中 $S:=\{a_k\}_{k=x}^y$。
实现细节
由于本题数据较多，您不需要输入输出，请完善以下程序中的 init(int, int, vector<int>) 和 solve(int, int) 函数，并提交。
void init(int n, int q, vector<int> a) {
// implement...
}
long long solve(int l, int r) {
// implement...
}你可以在下发文件中得到本题的样例交互库。
样例数据
样例 1 输入
5 10 2
0000000001000020000300004样例 1 输出
4834712607666044912样例 2 输入
20 100 16500242824326557842
0000500006000070000800000000010000200003000040000000001000020000300004000090000:0000;0000<0000=0000>样例 2 输出
5449866856465492064子任务
Idea：Powerless，Solution：ccz181078&noip&w33z，Code：w33z，Data：w33z
对于 $100\%$ 的数据，$1\leq n\le 6\times 10^5,1\le q\leq 10^6$，$0 \le a_i < 2^{30}$，$0 \le l \le r < n$。