P10891 [Bad Problem Cup Round 1] Eliminate Lao Ge

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

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: ```cpp 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: ```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; ```

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.

**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