問題文

$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)$ が存在することが証明できる。この値を求めよ。

注記

求める極限は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な $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$

入力

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

$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$ 点を獲得する。

上の方法では $2$ 回の操作により $0.7$ 点を獲得しており、$f(2) \\geq 0.7$ であることがわかります。

この場合、獲得できる総得点は $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