有 $n$ 个选手进行比赛，他们的能力值分别是 $a_1...a_n$，能力值越高的选手越强，定义一个选手的排名是 1+(能力值大于他的选手个数)。

如果单纯按照能力值排名的话看上去很公平，但是由于每个选手擅长的领域不同，所以根据题目类型的不同，选手的能力值会发生一定的变化，例如如果我们出 6 道计数题，那么对计数一窍不通的选手的能力值就可以视为 0。在本题中，题目的类型可以用一个非负整数 $k$ 表示，然后在该题目下，选手的能力值就会从 $x$ 变成 $x\operatorname{xor}k$。

现在你是某场比赛的出题人，你要通过出题来操控比赛，因此你有 $Q$ 个问题，其中第 $i$ 个问题 $(x_i,y_i)$ 表示你想知道是否存在一个数 $k$ 使得题目类型是 $k$ 时第 $x_i$ 个选手的排名恰好为 $y_i$。

定义 $ans_i$ 表示第 $i$ 个问题的答案，如果是 "是"，那么 $ans_i=1$，否则 $ans_i=0$。

为了减少输出的时间复杂度，你只需要求出 $\sum_{i=1}^{Q}ans_ii^2$，虽然该答案不是很大，但为了让这道题看上去更像是个计数题，你需要输出答案对 $998244353$ 取模后的值。

输入格式

第一行两个正整数 $n,Q$。

第二行 $n$ 个非负整数表示 $a_1....a_n$。

接下来 $Q$ 行，第 $i$ 行两个正整数 $x_i,y_i$，表示第 $i$ 次询问。

输出格式

输出一个非负整数，表示答案对 $998244353$ 取模后的值

样例数据

样例 1 输入

5 4
1 2 3 4 5
2 1
1 3
3 4
4 2

样例 1 输出

30

子任务

Task1(7pts)：$a_i< 2^{12}$。

Task2(18pts)：$n\leq 1000$。

Task3(15pts)：$n\leq 5000$。

Task4(20pts)：$Q\leq 50000$。

Task5(40pts)：无限制。

对于所有数据，都有 $1\leq n\leq 50000$，$0\leq a_i< 2^{60}$，$1\leq Q\leq 10^6$，$1\leq x_i,y_i \leq n$