随机更新查询

题目描述

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

我们将按 $i = 1, 2, \ldots, M$ 的顺序对 $A$ 执行如下操作。

首先,从 $L_i$ 到 $R_i$(含端点)之间均匀随机地选择一个整数,记为 $p$。

然后,将 $A_p$ 的值改为整数 $X_i$。

对于上述过程结束后的最终序列 $A$,输出 $A_i$ 的期望值对 $998244353$ 取模后的结果,其中 $i = 1, 2, \ldots, N$。

输入格式

输入按以下格式从标准输入给出:

$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$

输出格式

按如下格式用空格分隔输出最终的 $A_i$ 的期望值 $E_i$,其中 $i = 1, 2, \ldots, N$。

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

样例

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

499122179 1 665496238 665496236 5

从初始状态 $A = (3, 1, 4, 1, 5)$ 开始执行以下两次操作。

第一次操作以等概率选择 $A_1$ 或 $A_2$,并将其值改为 $2$。

然后,第二次操作以等概率选择 $A_2, A_3, A_4$ 中的一个,并将其值改为 $0$。

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

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

5 6

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

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

数据范围

• 所有输入值均为整数
• $1 \le N, M \le 2 \times 10^5$
• $0 \le A_i \le 10^9$
• $1 \le L_i \le R_i \le N$
• $0 \le X_i \le 10^9$

提示

关于期望值对 $998244353$ 取模的输出方法

可以证明,本题所求的期望值总是有理数。此外,本题的约束保证:若将这些期望值分别化为最简分数 $\frac{y}{x}$,则 $x$ 不被 $998244353$ 整除。

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