AT_arc126_e [ARC126E] Infinite Operations

[problemUrl]: https://atcoder.jp/contests/arc126/tasks/arc126_e $ 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 $ 番目のクエリで数列を変更した時点での、問題の答えを出力してください。

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