题目描述

你需要消灭劳嗝。

给定一个长度为 $n$ 的排列 $A=a_1,a_2,\cdots,a_n$，定义 $S_i=\{x|x\ge i\land \max_{i\le k\le x}a_k\le a_x\}$，您可以把它理解为以 $i$ 开头的后缀的前缀最大值的下标集合。例如对于 $A=\{3,5,2,1,4\}$，$S_1=\{1,2\}$，$S_3=\{3,5\}$。

有 $q$ 次询问，每次询问给出 $l,r$，求：

$$\left(\left(\sum_{l\le x\le y\le r} |S_x\cup S_y|-\sum_{\substack{{1\le x<l}\\{r<y\le n}}} |S_x\cup S_y|\right)\bmod P+P\right)\bmod P $$

其中，$P=998244353$。

输入格式

由于输入文件过大无法上传，接下来我们将会以一种诡异的方式读入数据。

第一行输入两个非负整数 $n$、$X$。表示排列长度、随机种子。

初始令 $a_i=i$，接下来输入一行一个整数 $c$，表示对排列的操作次数。

接下来我们将会对排列 $A$ 进行 $c$ 次操作，对于下标从 $1$ 开始的第 $i$ 次操作，令 $l=(X\times (X\oplus i))\bmod n+1,r=(X\oplus(i\times i))\bmod n+1$，你需要交换 $a_l$ 与 $a_r$。$\oplus$ 表示按位异或。

对于 C++，代码实现如下：

l = (1ll * X * (X ^ i)) % n + 1;
r = (X ^ (1ll * i * i)) % n + 1;

接下来输入一行一个整数 $q$，表示询问组数。

对于下标从 $1$ 开始的第 $i$ 次询问，我们令 $l=\min((X\times i+(X\oplus (X\times i)))\bmod n,(X-i+(X\oplus (X+i)))\bmod n)+1,r=\max((X\times i+(X\oplus (X\times i)))\bmod n,(X-i+(X\oplus (X+i)))\bmod n)+1$。表示询问的参数。

对于 C++，代码实现如下：

l = min((1ll * X * i + (X ^ (1ll * X * i))) % n, (X - i + (X ^ (X + i))) % n) + 1;
r = max((1ll * X * i + (X ^ (1ll * X * i))) % n, (X - i + (X ^ (X + i))) % n) + 1;

输出格式

由于输出文件过大无法上传，接下来我们将会以一种诡异的方式输出数据。

输出一行一个整数，表示 $q$ 次询问中所有答案的异或和。

5 3
4
5

998244304

10 114514
191981
3

998244191

提示

样例 1 解释：

操作后 $A=\{1,5,4,2,3\}$。

对询问解密后真实询问如下：

4 5
2 3
1 5
3 4
3 5

对输出解密后真实输出如下：

5
998244350
33
1
11

对于第一个询问，$S_4=\{4,5\}$，$S_5=\{5\}$，$|S_4\cup S_4|+|S_4\cup S_5|+|S_5\cup S_5|=5$。

对于倒数第二个询问，不要忘了 $1\le x<l,r<y\le n$ 的项。

数据范围

对于 $20\%$ 的数据，满足 $1\le n\le 100$、$1\le q\le 100$。

对于 $40\%$ 的数据，满足 $1\le n\le 100$、$1\le q\le 10^5$。

对于 $60\%$ 的数据，满足 $1\le n\le 10^5$、$1\le q\le 10^5$。

对于 $80\%$ 的数据，满足 $1\le n\le 3\times10^6$、$1\le q\le 3\times10^6$。

对于 $100\%$ 的数据，满足 $1\le n\le 10^7$，$1\le q\le 10^7$，$0\le c\le 10^7$，$0\le X\le 10^9$，$a_i$ 互不相同。

请各位选手注意常数因子的影响。