Problem Background

myy is touring Guangdong Foshan, so he came up with a Gaoming problem.

Problem Description

A point randomly moves on a sequence of length $n$ containing only 0s and 1s. The initial coordinate of the point is $p$. The following operations are repeated:
1. Stop the operation when the sequence is all 0s or all 1s.
2. Denote the current position of the point as $p$. Randomly select a point $q$ with equal probability, move the point to $q$, and invert the character at position $q$. Add the total cost by $f(|p-q|)$, where $f(x)=Ax^2+Bx$, and $A, B$ are given constants.
3. Return to the first step.

You need to perform $q$ modifications. Specifically, each modification includes:
1. Invert the 0/1 at the $\mathit{idx}$-th position of the sequence.
2. Query the expected cost after stopping the operation when the initial coordinate is $p$.

Note that modifications are permanent.

You need to output the XOR sum of the expected costs modulo $998244353$ for $q$ queries.

Considering the large input and output, the data is generated randomly as follows:

struct Random {
  unsigned long long X;
  void init(unsigned long long seed) { X = seed; }
  unsigned long long Rand() {
    X ^= X << 13;
    X ^= X >> 7;
    X ^= X << 17;
    return X;
  }
} R;

The initial 01 sequence is generated with $\mathit{seed1}$.

R.init(seed1);
for (int i = 1; i <= n; i++) seq[i] = R.Rand() & 1;

For $q$ queries, $\mathit{seed2}$ is provided.

R.init(seed2);
for (int i = 1; i <= q; i++) {
  idx = R.Rand() % n + 1, p = R.Rand() % n + 1;
  ans ^= query(idx, p);
}

Input Format

One line with six integers $n, q, \mathit{seed1}, \mathit{seed2}, A, B$, as described in the problem description.

Output Format

One line with an integer $\mathit{ans}$, representing the XOR sum of the expected costs modulo $998244353$ for $q$ queries.

Sample Input and Output

Sample Input #1

3 3 114514 1919810 0 1

Sample Output #1

831870297

Sample Input #2

5 3 998244353 1000000007 1 1

Sample Output #2

694472000

Sample Input #3

21 17 233 234 5 17

Sample Output #3

367211664

Notes

[Sample Explanation]

Explanation for Sample #1:
The three queries are: $110$, $p=3$, the answer is $\dfrac{11}{4}$; $010$, $p=3$, the answer is $\dfrac{17}{6}$; $110$, $p=1$, the answer is $\dfrac{11}{4}$. Under modulo $998244353$, they are $249561091$, $831870297$, and $249561091$ respectively, with an XOR sum of $831870297$.

[Data Range]

This problem uses subtask-based scoring.

For $100\%$ of the data, $3 \leq n \leq 3\times10^6$, $1 \leq q \leq 3\times10^6$, $0 \leq A, B < 998244353$, $\mathit{seed1}, \mathit{seed2} \in [0, 2^{64})$.

Special Condition A: $A = 0$.

As per convention, there should be an interesting postscript here, but given that you've cleared the monthly contest, you probably don't have the patience to read it, so there isn't one.

见题面 Input 部分

见题面 Output 部分