cats 的集合 2

Problem Description

此题输入/输出量较大，建议使用较快的读入方式，时间限制以关闭流同步的 cin/cout 为标准 cats 有一个大小为 $n$ 的可重集合 $S$，但是 cats 却不知道 $S$ 中的每个数分别是多少，只知道其中的第 $i$ 个数在 $[0, a_i]$ 中。定义 $S$ 的价值为集合中所有数的异或和，cats 认为一个集合有意义，当且仅当这个集合的价值在 $[L, R]$ 中。cats 想知道在 $S$ 的所有可能方案中，有多少方案满足 $S$ 是有意义的，由于 cats 并不确定 $L,R$ 的具体值，所以 cats 会进行多次询问。因为方案数可能会很大，你只需要输出答案对 $998244353$ 取模后得到的结果。

Input

第一行一个整数 $T$，表示测试组数（$1\leq T \leq 10$）。 对于每一组测试数据，第一行有两个整数 $n, m$（$1 \leq n, m \leq 10^6$）。 第二行 $n$ 个整数，第 $i$ 个整数表示 $a_i$（$0 \leq a_i \leq 10^{18}$）。 接下来有 $m$ 行，每行两个整数 $L, R$（$0 \leq L \leq R \leq 10^{18}$）。 保证 $\sum n \leq 2 \times 10^6, \sum m \leq 2 \times 10^6$ 。

Output

对于每组测试数据的每次询问，输出一行一个整数，表示答案。

Sample Input

2
2 2
1 2
0 0
1 2
4 1
2 3 5 7
2 7

Sample Output

2
3
432

Source

2024“钉耙编程”中国大学生算法设计超级联赛（8）