Background

In this world, “victory” is everything. The process does not matter.
No matter how many sacrifices it takes. As long as I “win” in the end, that is enough.

Problem Description

A new special exam is coming. This time the exam content is cultural courses (wan e de), but the difference is that students are allowed to use walkie-talkies during the exam. However, the receiving range of a walkie-talkie is limited (each walkie-talkie can transmit infinitely far, but can only receive signals within its receiving range), so not all students can receive broadcasts from other students.

During the exam, there are $n$ students sitting in a row (numbered from left to right as $1$ to $n$). Ayanokoji sits at position $c$. Each student has an ability value $w_i$. Ayanokoji has assigned each student a walkie-talkie with receiving range $d_i$.

Each student can directly solve all problems whose difficulty is not greater than their own ability value. Once a student solves a problem by their own ability, they will broadcast the solution to that problem. A student sitting at position $i$ with a walkie-talkie of receiving range $d_i$ can receive broadcasts from all students in the range $[i-d_i,\ i+d_i]$. If someone within this range has published the solution, then they will solve the problem too, and will also broadcast the solution.

Ayanokoji will ask you some questions: when a problem has difficulty $x$, how many students will solve it? Since Ayanokoji wants to hide his true strength, he may modify his own ability value. These two types of operations are represented as follows:

• $1\ x$: query how many students will solve a problem with difficulty $x$.
• $2\ x$: modify Ayanokoji's ability value to $x$, i.e., set $w_c$ to $x$.

Formal description (equivalent to the above):

You are given two sequences $w_{1..n}$ and $d_{1..n}$ of length $n$, and a position $c$ where $w_c$ can be modified. There are two types of operations (a total of $m$ times):

• $1\ x$ indicates 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}$. Here the definition of $f_i$ refers to $f_j$, so $f_{1..n}$ will keep updating until it can no longer be updated. The answer to this query is $\sum\limits_{i=1}^nf_i$.
• $2\ x$ indicates a modification: set $w_c$ to $x$.

Input Format

Because the data size is too large, to avoid slow input reading, the input is given using a pseudorandom number generator and is forced online.

It is recommended that you ignore the input format and directly use the data generator template provided below. Understanding the specific generation process is not necessary for you.

The first line contains three positive integers $n,\ m,\ c$, representing the total number of students, the total number of operations, and Ayanokoji's position.

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

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

In the next $k$ lines, each line contains two integers $p,\ t$, indicating that the receiving range of student $p$'s walkie-talkie (i.e., $d_p$) is adjusted to $t$.

If a student's walkie-talkie receiving range is adjusted multiple times, the last adjustment takes effect.

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()
{
	// 在读入种子后生成初始的 w 数组和 d 数组.
    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)
{
    // 生成一次操作的参数 opt 和 x, lastans 表示上一次询问的答案, 初始值为 0.
    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;
    }
    // 从这里开始，你可以使用生成的 w 数组和 d 数组.
    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
        {
            // 在这里执行修改操作.
        }
    }
    printf("%d\n", finalans);
    return 0;
}

Output Format

Let $ans_i$ denote the answer to the $i$-th query (operation $1$), and let $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$ be the number of queries (operation $1$). You only need to output one integer $T_q$.

3 3 2
19720918 0 1 2 0

700

10 10 8
2102036 0 1 4 1
5 2

760521825

1000 1000 126
114321251 1 2 2 0

91977056

Hint

Variables you will need:

$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 to generate the testdata:

$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 1:

Generated ability values for the three students are $w_{1..3} = \{0,\ 1,\ 2\}$, and the walkie-talkie receiving ranges are $d_{1..3} = \{1,\ 0,\ 1\}$.

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

Ayanokoji (student $2$) and student $3$ can solve it independently ($w_2 \ge 1$, $w_3 \ge 1$). Although student $1$ does not have enough ability, he can receive the solution broadcast by Ayanokoji through the walkie-talkie ($2 \in [1 - d_1,\ 1 + d_1]$), so he can solve it as well. Therefore $ans_1 = 3$.

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

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

Only student $3$ can solve it independently ($w_3 \ge 1$). However, neither student $1$ nor Ayanokoji (student $2$) can receive his broadcast solution ($3 \notin [1 - d_1,\ 1 + d_1]$, $3 \notin [2 - d_2,\ 2 + d_2]$), so they cannot solve it. Therefore $ans_2 = 1$.

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

Sample 2:

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

The ten operations and their corresponding results are as follows:

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

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

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

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

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

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

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

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

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

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

You only need to output $760521825$.

Sample 3:

The problem setter had enough conscience to write an explanation for this sample, but unfortunately the space is too small, so it cannot be written down.

Input Format

Output Format

Hint

Translated by ChatGPT 5