小苯的数组最值
题号：NC285674
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小苯有一个长度为 n 的数组 a，其中第 i 个数字的值为 a_i。

现在小苯会对 a 施加 m 个魔法，具体的，第 j 个魔法表示为 (l_j,r_j,d_j)，施法后会使得 a_l, a_{l+1},\cdots,a_r 这一段的数字都加上 d_j。

但身为见习魔法师的小苯法力并不稳定，具体来说这 m 个魔法并不会全部施法成功，而是会随机且等概的失效一个魔法，只有 m-1 个魔法施法成功，他想知道这样的情况下，数组 a 最大值的期望是多少，请你帮他算一算吧。

输入描述:

每个测试文件内都包含多组测试数据。
第一行一个正整数 T\ (1 \leq T \leq 1000)，表示测试数据的组数。
接下来对于每组测试数据，输入包含 m+2 行。
第一行两个整数 n,m\ (1 \leq n,m \leq 5 \times 10^5)，表示数组 a 的长度，以及小苯的施法次数。
第二行 n 个整数 a_i\ (1 \leq a_i \leq 10^9)，表示数组 a。
接下来m 行，每行三个正整数 l_j, r_j, d_j \ (1 \leq l_j \leq r_j \leq n, 0 \leq d_j \leq 10^9)，描述每一个魔法。
（保证所有测试数据中 n,m 的总和都不超过 5\times 10^5。）

输出描述:

对于每个测试数据，输出一行一个整数表示数组的最大值对 998244353 取模的值。
（分数取模的定义：可以证明，这个期望一定是一个有理数，如果写成 p/q 的形式，你输出的 a 需要保证 a*q 对 998244353 取模恰好等于 p。）
Python选手建议通过Pypy、Pypy3语言进行提交。
示例1

输入

复制 
1
3 3
1 1 1
1 1 2
2 2 3
3 3 4

输出

复制 
665496240

说明

初始数组为：\{1, 1, 1\}，
如果第一次魔法失效，则数组变为：\{1, 4, 5\}，最大值为 5。
如果第二次魔法失效，则数组变为：\{3, 1, 5\}，最大值为 5。
如果第三次魔法失效，则数组变为：\{3, 4, 1\}，最大值为 4。

因此数组最大值的期望为 \frac{14}{3}，对 998244353 取模后的结果为 665496240。