Problem Background

In this world, "victory" is everything. The process doesn't matter.
No matter how much sacrifice is involved, as long as I "win" in the end, that's all that matters.

Problem Description

A new special exam has arrived, and this time it involves (sinister) cultural subjects. However, the difference is that students are allowed to use walkie-talkies during the exam. The catch is that the reception range of the walkie-talkies is limited (each walkie-talkie can transmit infinitely far, but can only receive signals within its reception range), so not all students can receive broadcasts from others.

During the exam, there are $n$ students seated in a row (numbered from left to right as $1$ to $n$), with Ayanokouji himself seated at position $c$. Each student has a capability value $w_i$. Ayanokouji has arranged a walkie-talkie with a reception range of $d_i$ for each student.

Each student can directly solve all problems whose difficulty does not exceed their capability value. Once a student solves a problem by their capability, they will broadcast the solution. A student seated at position $i$ with a walkie-talkie having a reception range of $d_i$ can receive broadcasts from students within the range $[i-d_i, i+d_i]$. If someone within this range broadcasts a solution, they will also solve the problem and broadcast the solution.

Ayanokouji will ask you some questions: For a problem with difficulty $x$, how many students will be able to solve it? Since Ayanokouji wants to hide his strength, he might modify his own capability value. These operations are represented as follows:

• $1\ x$, indicating a query for how many students can solve a problem with difficulty $x$.
• $2\ x$, modifying Ayanokouji's capability value to $x$, i.e., changing $w_c$ to $x$.

Formal Description (same as above):

Given two sequences of length $n$, $w_{1..n}$ and $d_{1..n}$, and a position $c$ where $w_c$ can be modified. There are two types of operations (total $m$ times):
- $1\ x$ represents a query: Let $f_i=\begin{cases}1\quad(w_i\ge x)\\1\quad(\exists\ j \in [i - d_i,\ i + d_i],\ f_j=1)\\ 0\quad(otherwise)\end{cases}$, where $f_i$ references $f_j$, so $f_{1..n}$ updates continuously until no further updates are possible, and the answer to this query is $\sum\limits_{i=1}^nf_i$.
- $2\ x$ represents a modification: Change $w_c$ to $x$.

Input Format

Due to the large amount of data, to avoid excessive input time, input is provided via a pseudo-random number generator and is forced online.

It is recommended that you ignore the input format and directly use the data generator template provided below, as understanding the specific generation process is unnecessary for you.

The first line contains three positive integers $n$, $m$, and $c$, representing the total number of students, the total number of operations, and the position of Ayanokouji, respectively.

The second line contains five integers $\mathrm{seed}$, $\mathrm{mind}$, $\mathrm{maxd}$, $\mathrm{mfq}$, and $k$.

Here, $\mathrm{mind}$ and $\mathrm{maxd}$ are only used to generate the initial $d_{1..n}$, and the $t$ used to adjust $d_p$ may not be within $[\mathrm{mind}, \mathrm{maxd}]$.

The next $k$ lines, each containing two integers $p$ and $t$, indicate adjusting the walkie-talkie reception range (i.e., $d_p$) of the $p$-th student to $t$.

If a student's walkie-talkie reception range is adjusted multiple times, the last adjustment is valid.

Data Generator Template:

#include <cstdio>

unsigned long long seed;
int n, m, c, mfq, mind, maxd, k, w[2000001], d[2000001];

inline int randInt() { seed = 99999989 * seed + 1000000007; return seed >> 33; } 

void generate()
{
    for (int i = 1; i <= n; i++) { w[i] = randInt() % n; }
    for (int i = 1; i <= n; i++) { d[i] = randInt() % (maxd - mind + 1) + mind; }
}

void getOperation(int lastans, int &opt, int &x)
{
    if ((0ll + randInt() + lastans) % mfq) { opt = 1; } else { opt = 2; }
    x = (0ll + randInt() + lastans) % n;
}

int main()
{
    scanf("%d %d %d", &n, &m, &c);
    scanf("%llu %d %d %d %d", &seed, &mind, &maxd, &mfq, &k);
    generate();
    for (int i = 1; i <= k; i++)
    {
        int p, t;
        scanf("%d %d", &p, &t);
        d[p] = t;
    }
    int lastans = 0, finalans = 0;
    for (int i = 1; i <= m; i++)
    {
        int opt, x;
        getOperation(lastans, opt, x);
        if (opt == 1)
        {
            finalans = (finalans * 233ll + ___) % 998244353;
            lastans = ___;
        }
        else
        {
            // Execute modification operation.
        }
    }
    printf("%d\n", finalans);
    return 0;
}

Output Format

Let $ans_i$ represent the answer to the $i$-th query (operation $1$), and $T_i=\begin{cases}(T_{i-1}\times 233+ans_i)\mod 998244353\quad(i\ge 1)\\0\quad(i=0)\end{cases}$.

Let $q$ represent the number of queries (operation $1$), you only need to output an integer $T_q$.

Sample Input and Output

Sample Input #1

3 3 2
19720918 0 1 2 0

Sample Output #1

700

Sample Input #2

10 10 8
2102036 0 1 4 1
5 2

Sample Output #2

760521825

Sample Input #3

1000 1000 126
114321251 1 2 2 0

Sample Output #3

91977056

Notes/Hints

Variables You Need to Use:

$1\le c\le n\le 2\times 10^6$, $1\le m\le 2\times 10^6$, $0\le w_i, d_i, x<n$.

Other Variables Used for Data Generation:

$1\le \mathrm{seed}, \mathrm{mfq}\le 10^9$, $0\le \mathrm{mind}\le \mathrm{maxd}<n$, $0\le k\le 2\times 10^5$, $1\le p\le n$, $0\le t<n$.

Sample Explanation

Sample One:

Generated capability values $w_{1..3} = \{0, 1, 2\}$ and walkie-talkie reception ranges $d_{1..3} = \{1, 0, 1\}$.

The first operation is 1 1, querying how many students can solve a problem with difficulty $1$.

Ayanokouji (the 2nd student) and the 3rd student can independently solve this problem ($w_2 \ge 1$, $w_3 \ge 1$), and the 1st student, though lacking the capability, can receive the broadcast from Ayanokouji ($2 \in [1 - d_1, 1 + d_1$), so he can also solve it. Hence, $ans_1 = 3$.

The second operation is 2 0, modifying Ayanokouji's (the 2nd student) capability value to $0$. Now, $w_{1..3} = \{0, 0, 2\}$.

The third operation is 1 1, querying again how many students can solve a problem with difficulty $1$.

Only the 3rd student can independently solve it ($w_3 \ge 1$), but the 1st student and Ayanokouji (the 2nd student) cannot receive his broadcast ($3 \notin [1 - d_1, 1 + d_1]$, $3 \notin [2 - d_2, 2 + d_2]$) and cannot solve it. Hence, $ans_2 = 1$.

In summary, $T_1 = ans_1 = 3$, $T_2 = 3 \times T_1 + ans_2 = 3 \times 233 + 1 = 700$, output $700$ only.

Sample Two:

Generated $w_{1..10} = \{1, 6, 6, 5, 3, 5, 2, 7, 9, 5\}$ and $d_{1..10} =\{1, 1, 1, 1, 2, 0, 1, 0, 1, 1\}$.

Ten operations and their corresponding results are as follows:

1 6, query operation, $ans_1 = 9$, $T_1 = 9$.

2 2, modification operation, $w_{1..10}$ becomes $\{1, 6, 6, 5, 3, 5, 2, 2, 9, 5\}$.

1 7, query operation, $ans_2 = 2$, $T_2 = 2099$.

1 3, query operation, $ans_3 = 9$, $T_3 = 489076$.

2 4, modification operation, $w_{1..10}$ becomes $\{1, 6, 6, 5, 3, 5, 2, 4, 9, 5\}$.

1 3, query operation, $ans_4 = 10$, $T_4 = 113954718$.

2 2, modification operation, $w_{1..10}$ becomes $\{1, 6, 6, 5, 3, 5, 2, 2, 9, 5\}$.

1 9, query operation, $ans_5 = 2$, $T_5 = 597096118$.

1 0, query operation, $ans_6 = 10$, $T_6 = 367430437$.

1 3, query operation, $ans_7 = 9$, $T_7 = 760521825$.

Output $760521825$ only.

Sample Three:

The problem setter has enough conscience to write an explanation for this sample, but the space is too small to fit it.

见题面 Input 部分

见题面 Output 部分