Background

myy is traveling in Foshan, Guangdong, so he made a “Gaoming” problem.

Problem Description

A point performs a random walk on a $0/1$ sequence of length $n$. The point’s initial position is $p$. Repeat the following operations:

1. If the entire sequence consists of only one character, stop.
2. Let the point’s current position be $p$. Uniformly at random choose a position $q$, move the point to $q$, flip the character at $q$, and add $f(|p-q|)$ to the total cost, where $f(x)=Ax^2+Bx$, and $A,B$ are two given constants.
3. Go back to step 1.

You need to perform $q$ modifications. Specifically, each modification includes:

1. Flip the $0/1$ at position $\mathit{idx}$ in the sequence.
2. Query the expected cost after the process stops, when the initial position is $p$.

Note that once a modification is made, it remains effective.

You need to output the XOR sum of the answers to the $q$ queries, where each answer is the expected cost modulo $998244353$.

Since the input and output size is large, 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$ string is generated with $\mathit{seed1}$.

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

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

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$. Their meanings are described in “Description”.

Output Format

One line with one integer $\mathit{ans}$, representing the XOR sum of the $q$ query results, where each expected cost is taken modulo $998244353$.

3 3 114514 1919810 0 1

831870297

5 3 998244353 1000000007 1 1

694472000

21 17 233 234 5 17

367211664

Hint

[Sample Explanation]

Explanation for sample 1:
The three queries are: $110$, $p=3$, answer is $\dfrac{11}{4}$; $010$, $p=3$, answer is $\dfrac{17}{6}$; $110$, $p=1$, answer is $\dfrac{11}{4}$. Modulo $998244353$, they are $249561091$, $831870297$, and $249561091$, and the XOR sum is $831870297$.

[Constraints]

This problem uses subtask evaluation.

For $100\%$ of the testdata, $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 Property A: $A = 0$.

By convention, there should be an interesting postscript here, but since you have already finished the “Ake Monthly Contest”, you probably do not have the patience to read it, so there is none.

Translated by ChatGPT 5