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<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$ 个整数，用空格隔开。第 $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<998244353\ (1\leq i\leq N)$
• $1\leq L_i\leq R_i\leq N\ (1\leq i\leq M)$
• 输入均为整数

样例解释 1

例如，操作过程如下：

• 第 $1$ 次操作选中了 $4$。此时盘子 $1$ 到盘子 $7$ 上的石子数分别为 $30$、$10$、$40$、$150$、$0$、$0$、$20$。
• 第 $2$ 次操作选中了 $6$。此时盘子 $1$ 到盘子 $7$ 上的石子数分别为 $30$、$10$、$40$、$150$、$0$、$20$、$0$。
• 第 $3$ 次操作选中了 $2$。此时盘子 $1$ 到盘子 $7$ 上的石子数分别为 $0$、$250$、$0$、$0$、$0$、$0$、$0$。
• 第 $4$ 次操作选中了 $3$。此时盘子 $1$ 到盘子 $7$ 上的石子数分别为 $0$、$250$、$0$、$0$、$0$、$0$、$0$。

所有操作结束后，盘子 $1$、盘子 $2$ 上的石子期望数为 $35$，盘子 $3$、盘子 $4$、盘子 $5$、盘子 $6$、盘子 $7$ 上的石子期望数为 $36$，因此应输出 35 35 36 36 36 36 36。

样例解释 2

注意要对期望值取 $998244353$ 的模。所有操作结束后，每个盘子有 $\frac{1}{2}$ 的概率有 $1$ 个石子，$\frac{1}{2}$ 的概率没有石子。因此，石子的期望个数为 $\frac{1}{2}$。由于 $499122177\times 2\equiv 1\pmod{998244353}$，所以应输出 499122177 499122177。

由 ChatGPT 4.1 翻译