AT_abc417_f [ABC417F] Random Gathering

有 $N$ 个盘子，按照盘子 $1$、盘子 $2$、$\ldots$、盘子 $N$ 的顺序从左到右排列。最开始，盘子 $i$（$1\leq i\leq N$）中有 $A_i$ 个石子。 对这些盘子进行 $M$ 次操作。第 $i$ 次操作（$1\leq i\leq M$）会给出两个整数 $L_i, R_i$，依次进行如下操作： - 将盘子 $L_i$、盘子 $L_i+1$、$\ldots$、盘子 $R_i$ 这 $R_i-L_i+1$ 个盘子中的所有石子全部从盘子上取下。 - 从 $L_i$ 到 $R_i$ 之间的整数中等概率随机选取一个，记为 $x$。 - 将所有取下的石子全部放到盘子 $x$ 上。 对于 $i=1,2,\ldots,N$，请你求出 $M$ 次操作全部结束后，每个盘子 $i$ 上石子的期望个数，结果对 $998244353$ 取模。 所谓对 $998244353$ 取模的期望，是指期望值一定是有理数。在本题的约束下，若将其表示为最简分数 $\frac{P}{Q}$，则 $Q\not\equiv 0\pmod{998244353}$ 也成立。因此，存在唯一的整数 $R$ 满足 $R\times Q\equiv P\pmod{998244353},\ 0\leq R

输入按以下格式从标准输入读入。 > $N$ $M$ > $A_1$ $A_2$ $\ldots$ $A_N$ > $L_1$ $R_1$ > $L_2$ $R_2$ > $\vdots$ > $L_M$ $R_M$

请输出 $N$ 个整数，用空格隔开。第 $i$ 个（$1\leq i\leq N$）表示 $M$ 次操作全部结束后，盘子 $i$ 上石子的期望个数对 $998244353$ 取模的结果。

## 数据范围 - $1\leq N\leq 2\times 10^5$ - $1\leq M\leq 2\times 10^5$ - $0\leq A_i