AT_abc332_f [ABC332F] Random Update Query

[problemUrl]: https://atcoder.jp/contests/abc332/tasks/abc332_f 長さ $ N $ の整数列 $ A\ =\ (A_1,\ A_2,\ \ldots,\ A_N) $ が与えられます。 $ A $ に対して、$ i\ =\ 1,\ 2,\ \ldots,\ M $ の順に下記の操作を行います。 - まず、$ L_i $ 以上 $ R_i $ 以下の整数を等確率でランダムに $ 1 $ 個を選び、それを $ p $ とおく。 - そして、$ A_p $ の値を整数 $ X_i $ に変更する。 上記の手順を行った後の最終的な $ A $ における、$ A_i $ の期待値 $ \text{mod\ }\ 998244353 $ を、 各 $ i\ =\ 1,\ 2,\ \ldots,\ N $ について出力してください。 期待値 $ \text{mod\ }\ 998244353 $ の定義この問題で求める期待値は必ず有理数になることが証明できます。 また、この問題の制約下では、求める期待値を既約分数 $ \frac{y}{x} $ で表したときに $ x $ が $ 998244353 $ で割り切れないことが保証されます。 このとき $ xz\ \equiv\ y\ \pmod{998244353} $ を満たすような $ 0 $ 以上 $ 998244352 $ 以下の整数 $ z $ が一意に定まります。この $ z $ を答えてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ L_1 $ $ R_1 $ $ X_1 $ $ L_2 $ $ R_2 $ $ X_2 $ $ \vdots $ $ L_M $ $ R_M $ $ X_M $

各 $ i\ =\ 1,\ 2,\ \ldots,\ N $ に対する最終的な $ A_i $ の期待値 $ E_i $ を、 下記の形式の通りに空白区切りで出力せよ。 > $ E_1 $ $ E_2 $ $ \ldots $ $ E_N $

### 制約 - 入力される値は全て整数 - $ 1\ \leq\ N,\ M\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ A_i\ \leq\ 10^9 $ - $ 1\ \leq\ L_i\ \leq\ R_i\ \leq\ N $ - $ 0\ \leq\ X_i\ \leq\ 10^9 $ ### Sample Explanation 1 $ A\ =\ (3,\ 1,\ 4,\ 1,\ 5) $ である初期状態からはじめ、下記の通りに $ 2 $ 個の操作が行われます。 - まず、$ 1 $ 個目の操作で、$ A_1 $ と $ A_2 $ のどちらか一方が等確率でランダムに選ばれ、その値が $ 2 $ に変更されます。 - その後、$ 2 $ 個目の操作で、$ A_2,\ A_3,\ A_4 $ のうちいずれか $ 1 $ 個が等確率でランダムに選ばれ、その値が $ 0 $ に変更されます。 その結果、最終的な $ A $ の各要素の期待値は $ (E_1,\ E_2,\ E_3,\ E_4,\ E_5)\ =\ (\frac{5}{2},\ 1,\ \frac{8}{3},\ \frac{2}{3},\ 5) $ です。