Problem Description

You need to eliminate "劳嗝" (a fictional problem element).

Given a permutation \( A = a_1, a_2, \cdots, a_n \) of length \( n \), define \( S_i = \{ x \mid x \ge i \land \max_{i \le k \le x} a_k \le a_x \} \), which can be understood as the set of indices of the prefix maximum values starting from \( 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 provides \( l, r \), and you need to find:

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

Due to the large size of the input file, data will be read in an unusual manner.

The first line contains two non-negative integers \( n \) and \( X \). This indicates the length of the permutation and the random seed.

Initialize \( a_i = i \). The next line contains an integer \( c \), indicating the number of operations on the permutation.

The permutation \( A \) will undergo \( c \) operations. For the \( i \)-th operation (starting from 1), 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 the bitwise XOR operation.

For C++, the implementation is as follows:

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

The next line contains an integer \( q \), indicating the number of queries.

For the \( i \)-th query (starting from 1), 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 parameters for the query.

For C++, the implementation 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

Due to the large size of the output file, data will be output in an unusual manner.

Output a single integer, which is the XOR sum of the answers for all \( q \) queries.

Sample Input and Output

Sample Input #1

5 3
4
5

Sample Output #1

998244304

Sample Input #2

10 114514
191981
3

Sample Output #2

998244191

Notes/Hints

Sample 1 Explanation:

After operations, \( A = \{1, 5, 4, 2, 3\} \).

The decrypted queries are as follows:

4 5
2 3
1 5
3 4
3 5

The decrypted output is as follows:

5
998244350
33
1
11

For the first query, \( S_4 = \{4, 5\} \), \( S_5 = \{5\} \), \( |S_4 \cup S_4| + |S_4 \cup S_5| + |S_5 \cup S_5| = 5 \).

For the second-to-last query, do not forget the terms where \( 1 \le x < l \) and \( r < y \le n \).

Data Range:

• For 20% of the data, \( 1 \le n \le 100 \), \( 1 \le q \le 100 \).
• For 40% of the data, \( 1 \le n \le 100 \), \( 1 \le q \le 10^5 \).
• For 60% of the data, \( 1 \le n \le 10^5 \), \( 1 \le q \le 10^5 \).
• For 80% of the data, \( 1 \le n \le 3 \times 10^6 \), \( 1 \le q \le 3 \times 10^6 \).
• For 100% of the data, \( 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 \( a_i \) are distinct.

Please note the impact of constant factors.

见题面 Input 部分

见题面 Output 部分