AT_abc417_f [ABC417F] Random Gathering

$ N $ 個の皿が、皿 $ 1, $ 皿 $ 2,\ldots, $ 皿 $ N $ の順に左から並んでいます。 はじめ、皿 $ i\ (1\le i\le N) $ には $ A _ i $ 個の石が入っています。 この皿たちに対して $ M $ 回の操作を行います。 $ i $ 回目 $ (1\le i\le M) $ の操作では、 $ 2 $ つの整数 $ L _ i,R _ i $ が与えられ、次の操作を順に行います。 - 皿 $ L _ i, $ 皿 $ L _ i+1,\ldots, $ 皿 $ R _ i $ の $ R _ i-L _ i+1 $ 個の皿に入っている石をすべて皿の上から取り除く。 - $ L _ i $ 以上 $ R _ i $ 以下の整数を一様ランダムに $ 1 $ つ取り、それを $ x $ とする。 - 取り除いた石をすべて皿 $ x $ に乗せる。 $ i=1,2,\ldots,N $ について、 $ M $ 回の操作がすべて終了したときに皿 $ i $ に置かれている石の個数の期待値を $ {}\bmod998244353 $ で求めてください。 期待値を $ {}\bmod{998244353} $ で求めるとは求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 $ \frac{P}{Q} $ で表した時、 $ Q \not\equiv 0 \pmod{998244353} $ となることも証明できます。 よって、 $ R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353 $ を満たす整数 $ R $ が一意に定まります。期待値を $ {}\bmod{998244353} $ で求めるとは、この $ R $ を求めることを指します。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A _ 1 $ $ A _ 2 $ $ \ldots $ $ A _ N $ $ L _ 1 $ $ R _ 1 $ $ L _ 2 $ $ R _ 2 $ $ \vdots $ $ L _ M $ $ R _ M $

空白を区切りとして $ N $ 個の整数を $ 1 $ 行に出力せよ。 $ i $ 番目 $ (1\leq i\leq N) $ には $ M $ 回の操作がすべて終了したときに皿 $ i $ に置かれている石の個数の期待値を $ {}\bmod998244353 $ で求め、出力せよ。

### Sample Explanation 1 例えば、操作は次のように進みます。 - $ 1 $ 回目の操作で $ 4 $ が選ばれる。皿 $ 1, $ 皿 $ 2,\ldots, $ 皿 $ 7 $ に置かれている石の個数はそれぞれ $ 30 $ 個 $ ,10 $ 個 $ ,40 $ 個 $ ,150 $ 個 $ ,0 $ 個 $ ,0 $ 個 $ ,20 $ 個となる。 - $ 2 $ 回目の操作で $ 6 $ が選ばれる。皿 $ 1, $ 皿 $ 2,\ldots, $ 皿 $ 7 $ に置かれている石の個数はそれぞれ $ 30 $ 個 $ ,10 $ 個 $ ,40 $ 個 $ ,150 $ 個 $ ,0 $ 個 $ ,20 $ 個 $ ,0 $ 個となる。 - $ 3 $ 回目の操作で $ 2 $ が選ばれる。皿 $ 1, $ 皿 $ 2,\ldots, $ 皿 $ 7 $ に置かれている石の個数はそれぞれ $ 0 $ 個 $ ,250 $ 個 $ ,0 $ 個 $ ,0 $ 個 $ ,0 $ 個 $ ,0 $ 個 $ ,0 $ 個となる。 - $ 4 $ 回目の操作で $ 3 $ が選ばれる。皿 $ 1, $ 皿 $ 2,\ldots, $ 皿 $ 7 $ に置かれている石の個数はそれぞれ $ 0 $ 個 $ ,250 $ 個 $ ,0 $ 個 $ ,0 $ 個 $ ,0 $ 個 $ ,0 $ 個 $ ,0 $ 個となる。 すべての操作が終了したときに皿 $ 1, $ 皿 $ 2 $ に置かれている石の個数の期待値は $ 35 $ 、皿 $ 3, $ 皿 $ 4, $ 皿 $ 5, $ 皿 $ 6, $ 皿 $ 7 $ に置かれている石の個数の期待値は $ 36 $ なので、`35 35 36 36 36 36 36` を出力してください。 ### Sample Explanation 2 期待値を $ {}\bmod998244353 $ で求めることに注意してください。 すべての操作が終了したとき、どちらの皿についても $ \dfrac12 $ の確率で石が $ 1 $ つ置かれており、 $ \dfrac12 $ の確率で石が $ 1 $ つも置かれていません。 よって、置かれている石の個数の期待値は $ \dfrac12 $ です。 $ 499122177\times2\equiv1\pmod{998244353} $ なので、`499122177 499122177` を出力してください。 ### Constraints - $ 1\le N\le2\times10 ^ 5 $ - $ 1\le M\le2\times10 ^ 5 $ - $ 0\le A _ i\lt998244353\ (1\le i\le N) $ - $ 1\le L _ i\le R _ i\le N\ (1\le i\le M) $ - 入力はすべて整数