【烂题杯 Round 1】消灭劳嗝

你需要消灭劳嗝。 给定一个长度为 $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++，代码实现如下： ```cpp 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++，代码实现如下： ```cpp 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$ 互不相同。 **请各位选手注意常数因子的影响。**