题目描述

有一台环形收音机，共有奇素数 $p$ 个档位，依次编号为 $0,1,\ldots,p-1$。旋钮转过一圈后会回到原位置，初始位于档位 $0$。

每次旋转时，只能顺时针转动一个非零二次剩余所对应的档位数。也就是说，一次旋转的改变量必须属于集合

$R=\{x^2\bmod p\mid 1\le x<p\}$。

由于 $p$ 是奇素数，$R$ 中恰有 $(p-1)/2$ 个不同元素，并且 $0\notin R$。

共有 $Q$ 次询问。第 $i$ 次询问给出两个整数 $k_i,n_i$，你需要求：从档位 $0$ 出发，恰好进行 $k_i$ 次旋转后到达档位 $n_i$ 的旋转方案数。

一个方案由每一步的档位改变量序列唯一确定。若第 $j$ 步选择的改变量为 $r_j\in R$，则需要满足

$r_1+r_2+\cdots+r_{k_i}\equiv n_i\pmod p$。

设第 $i$ 次询问的方案数为 $ans_i$。你不需要分别输出每个 $ans_i$，而是输出

$\displaystyle \bigoplus_{i=1}^{Q}(ans_i\bmod 998244353)$，

其中 $\oplus$ 表示按位异或。

输入格式

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

接下来 $Q$ 行，每行两个非负整数 $k_i,n_i$。

输出格式

输出一个整数，表示所有询问答案模 $998244353$ 后的按位异或和。

输入输出样例 #1

输入

3 7
0 0
1 1
2 5

输出

2

说明

当 $p=7$ 时，非零二次剩余为 $\{1,2,4\}$。

• $k=0,n=0$：只有空序列，方案数为 $1$；
• $k=1,n=1$：只有 $(1)$，方案数为 $1$；
• $k=2,n=5$：有 $(1,4)$、$(4,1)$ 两种方案，方案数为 $2$。

因此最终答案为 $1\oplus1\oplus2=2$。

输入输出样例 #2

输入

7 11
0 0
1 1
1 2
2 0
2 1
2 2
3 0

输出

14

数据范围与约定

对于全部数据：

• $1\le Q\le10^5$；
• $p$ 为奇素数；
• $0\le n_i<p\le10^9$；
• $0\le k_i\le10^{18}$。

原题各测试点覆盖的典型性质包括：

原数据还同时覆盖 $p\equiv1\pmod4$ 与 $p\equiv3\pmod4$ 两种情况。

提示

对于固定的 $p$ 和 $k$，答案只与 $n$ 属于以下三类中的哪一类有关：

1. $n=0$；
2. $n$ 是非零二次剩余；
3. $n$ 是非二次剩余。

这三类之间可以建立一个 $3\times3$ 的线性递推。