AT_abc417_f [ABC417F] Random Gathering

There are $ N $ plates arranged from left to right as plate $ 1, $ plate $ 2,\ldots, $ plate $ N $ . Initially, plate $ i\ (1\le i\le N) $ contains $ A _ i $ stones. You will perform $ M $ operations on these plates. In the $ i $ -th operation $ (1\le i\le M) $ , two integers $ L _ i $ and $ R _ i $ are given, and the following operations are performed in order: - Remove all stones from the $ R _ i-L _ i+1 $ plates: plate $ L _ i, $ plate $ L _ i+1,\ldots, $ plate $ R _ i $ . - Uniformly randomly choose an integer between $ L _ i $ and $ R _ i $ , inclusive, and let it be $ x $ . - Place all the removed stones on plate $ x $ . For $ i=1,2,\ldots,N $ , find the expected number, modulo $ 998244353 $ , of stones placed on plate $ i $ when all $ M $ operations are completed. Finding expected value modulo $ 998244353 $ It can be proved that the expected value you seek is always a rational number. Also, under the constraints of this problem, when that value is expressed as an irreducible fraction $ \frac{P}{Q} $ , it can be proved that $ Q \not\equiv 0 \pmod{998244353} $ . Therefore, there is a unique integer $ R $ such that $ R \times Q \equiv P \pmod{998244353}, 0 \leq R \lt 998244353 $ . Finding the expected value modulo $ 998244353 $ means finding this $ R $ .

The input is given from Standard Input in the following format: > $ N $ $ M $ $ A _ 1 $ $ A _ 2 $ $ \ldots $ $ A _ N $ $ L _ 1 $ $ R _ 1 $ $ L _ 2 $ $ R _ 2 $ $ \vdots $ $ L _ M $ $ R _ M $

Output $ N $ integers separated by spaces on a single line. For the $ i $ -th $ (1\leq i\leq N) $ , find the expected number, modulo $ 998244353 $ , of stones placed on plate $ i $ when all $ M $ operations are completed, and output it.

### Sample Explanation 1 For example, the operations proceed as follows: - In the first operation, $ 4 $ is chosen. The number of stones on plates $ 1, $ $ 2,\ldots, $ $ 7 $ becomes $ 30 $ , $ 10 $ , $ 40 $ , $ 150 $ , $ 0 $ , $ 0 $ , $ 20 $ , respectively. - In the second operation, $ 6 $ is chosen. The number of stones on plates $ 1, $ $ 2,\ldots, $ $ 7 $ becomes $ 30 $ , $ 10 $ , $ 40 $ , $ 150 $ , $ 0 $ , $ 20 $ , $ 0 $ , respectively. - In the third operation, $ 2 $ is chosen. The number of stones on plates $ 1, $ $ 2,\ldots, $ $ 7 $ becomes $ 0 $ , $ 250 $ , $ 0 $ , $ 0 $ , $ 0 $ , $ 0 $ , $ 0 $ , respectively. - In the fourth operation, $ 3 $ is chosen. The number of stones on plates $ 1, $ $ 2,\ldots, $ $ 7 $ becomes $ 0 $ , $ 250 $ , $ 0 $ , $ 0 $ , $ 0 $ , $ 0 $ , $ 0 $ , respectively. When all operations are completed, the expected number of stones on plates $ 1, $ $ 2 $ is $ 35 $ , and the expected number of stones on plates $ 3, $ $ 4, $ $ 5, $ $ 6, $ $ 7 $ is $ 36 $ , so output `35 35 36 36 36 36 36`. ### Sample Explanation 2 Note that you need to find the expected value modulo $ 998244353 $ . When all operations are completed, for both plates, there is a $ \dfrac12 $ probability that one stone is placed, and a $ \dfrac12 $ probability that no stone is placed. Therefore, the expected number of stones placed is $ \dfrac12 $ . We have $ 499122177\times2\equiv1\pmod{998244353} $ , so output `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) $ - All input values are integers.