题目描述

给定一个长度为$N$的整数序列$A = (A_1, A_2, \ldots, A_N)$。

我们将按顺序对$A$执行$i = 1, 2, \ldots, M$次操作，每次操作的具体步骤如下：

1. 首先，在$[L_i, R_i]$范围内均匀随机选择一个整数，记为$p$；
2. 然后，将$A_p$的值修改为整数$X_i$。

对于经过上述所有操作后的最终序列$A$，请输出每个位置$i = 1, 2, \ldots, N$上$A_i$的期望值，并将结果对$998244353$取模。

关于期望值取模的输出规则

可以证明，本题所求的期望值一定是有理数。此外，题目约束保证：若将每个期望值表示为最简分数$\frac{y}{x}$，则$x$不被$998244353$整除。

存在唯一的整数$z$满足$0 \leq z \leq 998244352$，且$xz \equiv y \pmod{998244353}$，请输出这个$z$。

题目约束

• 所有输入值均为整数；
• $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$。

输入格式

输入数据从标准输入按以下格式给出：

$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$的期望值$E_i$（对$998244353$取模后的值），相邻值之间用空格分隔：

$E_1$ $E_2$ $\ldots$ $E_N$

样例输入1

5 2
3 1 4 1 5
1 2 2
2 4 0

样例输出1

499122179 1 665496238 665496236 5

样例解释1

初始序列为$A = (3, 1, 4, 1, 5)$，执行两次操作：

1. 第一次操作：从$A_1$或$A_2$中均匀随机选一个，将其值改为$2$；
2. 第二次操作：从$A_2、A_3、A_4$中均匀随机选一个，将其值改为$0$。

最终序列各元素的期望值为$(E_1, E_2, E_3, E_4, E_5) = (\frac{5}{2}, 1, \frac{8}{3}, \frac{2}{3}, 5)$。

• $\frac{5}{2}$ 模$998244353$的结果为$499122179$（因为$2 \times 499122179 \equiv 5 \pmod{998244353}$）；
• $\frac{8}{3}$ 模$998244353$的结果为$665496238$；
• $\frac{2}{3}$ 模$998244353$的结果为$665496236$。

样例输入2

2 4
1 2
1 1 3
2 2 4
1 1 5
2 2 6

样例输出2

5 6

样例解释2

每次操作的区间都是单元素（$[1,1]$或$[2,2]$），因此随机选择的位置是确定的：

• 位置1依次被修改为3、5，最终值确定为5；
• 位置2依次被修改为4、6，最终值确定为6；
• 因此期望值就是确定值5和6。

样例输入3

20 20
998769066 273215338 827984962 78974225 994243956 791478211 891861897 680427073 993663022 219733184 570206440 43712322 66791680 164318676 209536492 137458233 289158777 461179891 612373851 330908158
12 18 769877494
9 13 689822685
6 13 180913148
2 16 525285434
2 14 98115570
14 17 622616620
8 12 476462455
13 17 872412050
14 15 564176146
7 13 143650548
2 5 180435257
4 10 82903366
1 2 643996562
8 10 262860196
10 14 624081934
11 13 581257775
9 19 381806138
3 12 427930466
6 19 18249485
14 19 682428942

样例输出3

821382814 987210378 819486592 142238362 447960587 678128197 687469071 405316549 318941070 457450677 426617745 712263899 939619994 228431878 307695685 196179692 241456697 12668393 685902422 330908158