Contest Duration: - (local time) (120 minutes) Back to Home
E - Infinite Operations /

Time Limit: 5 sec / Memory Limit: 1024 MB

問題文

N 項からなる正整数列 A = (A_1, A_2, \ldots, A_N)Q 個のクエリが与えられます。i 番目のクエリは、以下のようなものです：

• 整数 x_i, y_i （ただし 1\leq x_i\leq N）が与えられる。A_{x_i}y_i に変更する。

クエリで数列が変更されるたびに、以下の問題の答えを \mod 998244353 で求めてください（注記参照）。

• A_i\leq A_j となる i, j および A_i + 2x \leq A_j となる非負実数 x を選ぶ。
• A_ix を加え、A_j から x を引く。
• x 点を獲得する。

制約

• 2\leq N\leq 3\times 10^5
• 1\leq Q\leq 3\times 10^5
• 1\leq A_i \leq 10^9
• 1\leq x_i\leq N
• 1\leq y_i\leq 10^9

入力

N Q
A_1 A_2 \ldots A_N
x_1 y_1
\vdots
x_Q y_Q


出力

Q 行出力してください。i 行目には、i 番目のクエリで数列を変更した時点での、問題の答えを出力してください。

入力例 1

3 4
7 5 5
1 5
2 6
1 7
3 5


出力例 1

0
1
2
2


1 つめのクエリにより、数列は (5, 5, 5) へと変更されます。この場合任意の n に対して f(n) = 0 となり、答えは 0 となります。

2 つめのクエリにより、数列は (5,6,5) へと変更されます。操作は例えば以下のように進行します。

• (i,j,x) = (3,2,0.4) と選ぶ。数列を (5, 5.6, 5.4) へ変更し、0.4 点を獲得する。
• (i,j,x) = (1,2,0.3) と選ぶ。数列を (5.3, 5.3, 5.4) へ変更し、0.3 点を獲得する。

この場合、獲得できる総得点は 1 を超えることはなく、操作回数を増やしていき最適な方法で操作を行うことで、獲得できる総得点を限りなく 1 に近づけることが可能であることが証明できます。したがって \displaystyle \lim_{n\to\infty} f(n) = 1 となります。

入力例 2

2 4
1 2
2 5
1 3
1 2
2 3


出力例 2

2
1
499122178
499122177


Score : 800 points

Problem Statement

Given are a sequence of N positive integers A = (A_1, A_2, \ldots, A_N) and Q queries. The i-th query is as follows:

• given integers x_i and y_i (where 1\leq x_i\leq N), change A_{x_i} to y_i.

Each time the query changes the sequence, find the answer to the following problem modulo 998244353 (see Notes).

Let f(n) be the maximum total number of points when doing the following operation n times on A.

• Choose i, j such that A_i\leq A_j and choose non-negative real number x such that A_i + 2x \leq A_j.
• Add x to A_i and subtract x from A_j.
• Gain x points.

It can be proved that the limit \displaystyle \lim_{n\to\infty} f(n) exists. Find this limit.

Notes

We can prove that the limit in question is always a rational number. Additionally, under the Constraints of this problem, when that number is represented as \frac{P}{Q} using two coprime integers P and Q, we can prove that there is a unique integer R such that R\times Q\equiv P\pmod{998244353} and 0\leq R < 998244353. Find this R.

Constraints

• 2\leq N\leq 3\times 10^5
• 1\leq Q\leq 3\times 10^5
• 1\leq A_i \leq 10^9
• 1\leq x_i\leq N
• 1\leq y_i\leq 10^9

Input

Input is given from Standard Input in the following format:

N Q
A_1 A_2 \ldots A_N
x_1 y_1
\vdots
x_Q y_Q


Output

Print Q lines; the i-th line should contain the answer to the problem just after the change by the i-th query.

Sample Input 1

3 4
7 5 5
1 5
2 6
1 7
3 5


Sample Output 1

0
1
2
2


The first query changes the sequence to (5, 5, 5). Here, we have f(n) = 0 for any n, so the answer is 0.

The second query changes the sequence to (5, 6, 5). Here, one possible way to do the operations is as follows.

• Choose (i,j,x) = (3,2,0.4), changing the sequence to (5, 5.6, 5.4) and gaining 0.4 points.
• Choose (i,j,x) = (1,2,0.3), changing the sequence to (5.3, 5.3, 5.4) and gaining 0.3 points.

The above two operations gain 0.7 points, from which we can see that f(2) \geq 0.7.

We can prove that it is impossible to gain more than 1 point in total, and that the total number of points that can be gained by the optimal way to do the operations tends to 1 as the number of operations increases. Thus, we have \displaystyle \lim_{n\to\infty} f(n) = 1.

Sample Input 2

2 4
1 2
2 5
1 3
1 2
2 3


Sample Output 2

2
1
499122178
499122177