题目描述

$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$ に対して以下の操作を $n$ 回行うとき、獲得できる総得点の最大値を $f(n)$ とする。

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

極限 $\displaystyle\ \lim_{n\to\infty}\ f(n)$ が存在することが証明できる。この値を求めよ。

输入格式

入力は以下の形式で標準入力から与えられます。

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

输出格式

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

题目大意

给定一个长度为 $n$ 的正整数序列 $a$ 和 $q$ 个操作，第 $i$ 个操作为如下：

• 给定 $x,y$，将 $a_x\to y$

每一次操作后输出这个序列的最大价值，价值定义如下：每一次选择 $i,j$ 满足 $a_i\le a_j$，找到一个非负实数 $x$ 满足 $a_i+2x\le a_j$，将 $a_i\to a_i+x,a_j\to a_j-x$，得到 $x$ 的价值，价值可以累加。你可以重复这个操作多次。可以证明最大的总价值收敛到一个有理数，输出这个有理数对 $998244353$ 取模的值。

• $2\le n,q\le 3\times 10^5,a_i\le 10^9$

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

0
1
2
2

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

2
1
499122178
499122177

提示

注記

求める極限は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な $2$ つの整数 $P,\ Q$ を用いて $\frac{P}{Q}$ と表したとき、$R\times\ Q\equiv\ P\pmod{998244353}$ かつ $0\leq\ R\ <\ 998244353$ を満たす整数 $R$ がただ一つ存在することが証明できます。この $R$ を求めてください。

制約

• $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$

Sample Explanation 1

$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$ 点を獲得する。 上の方法では $2$ 回の操作により $0.7$ 点を獲得しており、$f(2)\ \geq\ 0.7$ であることがわかります。 この場合、獲得できる総得点は $1$ を超えることはなく、操作回数を増やしていき最適な方法で操作を行うことで、獲得できる総得点を限りなく $1$ に近づけることが可能であることが証明できます。したがって $\displaystyle\ \lim_{n\to\infty}\ f(n)\ =\ 1$ となります。