Super big cup
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小七是《昨夜圆车》的数值策划，他正在为新干员的数值调整做准备。新干员有n项数值，第i项数值初始为a_i。为了优化游戏体验，小七计划对这些数值进行 m次随机调整操作，具体规则如下：
  • 首先，在 l 和 r （含）之间均匀随机地选择一个整数，并将其记为 p 。
  • 然后，将 a_p 的值改为整数 x 。
m次操作后，小七想知道每个数值的期望是多少，所以你需要输出每项的期望值并模 998244353 。
可以证明，本题所求的期望值总是有理数。
期望：若一项数值可能取值为 x_1,x_2,\cdots,x_n，对应的概率为 P(x_1),P(x_2),\cdots,P(x_n) ，期望值 E(x)的计算公式为：E(x) = \sum \limits_{i=1}^{n} x_i \cdot P(x_i).

输入描述:

    第一行输入两个整数n,m( 1 \leq n, m \leq 2 \times 10^5)，分别表示数值项数和操作次数。
    第二行输入n个整数a_1,a_2,\cdots,a_n(1 \leq a_i \leq 10^9)表示各项数值的初始值。
    此后m行，每行输入三个整数l_i,r_i,x_i(1 \leq l_i \leq r_i \leq n,0 \leq x_i \leq 10^9)代表一次操作。

输出描述:

      对于每一个数据，在一行上输出n个整数，第i个数表示a中第i个数最终值的期望。
示例1

输入

复制 
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

输入

复制 
2 4
1 2
1 1 3
2 2 4
1 1 5
2 2 6

输出

复制 
5 6