Problem Description

You need to eliminate Lao Ge.

Given a permutation $A=a_1,a_2,\cdots,a_n$ of length $n$, define $S_i=\{x|x\ge i\land \max_{i\le k\le x}a_k\le a_x\}$. You may understand it as the set of indices of prefix maximums in the suffix starting at $i$. For example, for $A=\{3,5,2,1,4\}$, $S_1=\{1,2\}$ and $S_3=\{3,5\}$.

There are $q$ queries. Each query gives $l,r$, and you need to compute:

$$\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$$

where $P=998244353$.

Input Format

Since the input file is too large to upload, we will read the data in a weird way.

The first line contains two non-negative integers $n$ and $X$, representing the permutation length and the random seed.

Initially let $a_i=i$. Next, an integer $c$ is given in one line, representing the number of operations on the permutation.

Next, we will perform $c$ operations on the permutation $A$. For the $i$-th operation (1-indexed), let $l=(X\times (X\oplus i))\bmod n+1$ and $r=(X\oplus(i\times i))\bmod n+1$. You need to swap $a_l$ and $a_r$. Here $\oplus$ denotes bitwise XOR.

For C++, the code is as follows:

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

Next, an integer $q$ is given in one line, representing the number of queries.

For the $i$-th query (1-indexed), let $l=\min((X\times i+(X\oplus (X\times i)))\bmod n,(X-i+(X\oplus (X+i)))\bmod n)+1$ and $r=\max((X\times i+(X\oplus (X\times i)))\bmod n,(X-i+(X\oplus (X+i)))\bmod n)+1$. These are the query parameters.

For C++, the code is as follows:

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;

Output Format

Since the output file is too large to upload, we will output the data in a weird way.

Output one line with one integer, representing the XOR of all answers over the $q$ queries.

5 3
4
5

998244304

10 114514
191981
3

998244191

Hint

Sample 1 Explanation:

After the operations, $A=\{1,5,4,2,3\}$.

After decrypting the queries, the real queries are as follows:

4 5
2 3
1 5
3 4
3 5

After decrypting the output, the real output is as follows:

5
998244350
33
1
11

For the first query, $S_4=\{4,5\}$ and $S_5=\{5\}$. Then $|S_4\cup S_4|+|S_4\cup S_5|+|S_5\cup S_5|=5$.

For the second last query, do not forget the terms with $1\le x<l,r<y\le n$.

Constraints:

For $20\%$ of the testdata, $1\le n\le 100$ and $1\le q\le 100$.

For $40\%$ of the testdata, $1\le n\le 100$ and $1\le q\le 10^5$.

For $60\%$ of the testdata, $1\le n\le 10^5$ and $1\le q\le 10^5$.

For $80\%$ of the testdata, $1\le n\le 3\times10^6$ and $1\le q\le 3\times10^6$.

For $100\%$ of the testdata, $1\le n\le 10^7$, $1\le q\le 10^7$, $0\le c\le 10^7$, $0\le X\le 10^9$, and all $a_i$ are distinct.

All contestants should pay attention to the impact of constant factors.

Translated by ChatGPT 5