Orange的失效线段树

题目描述

Orange刚刚学会了线段树，他想用线段树来解决一个区间最值问题，于是他马上写了一颗线段树。这颗线段树对于一个长度为 $n$ 的序列 $a_i$，支持区间加法和区间查询最大值。

区间加法指的是：对于序列 $a$ 的一个区间 $a[l,...,r]$，将每个数依次加上一个定值 $d$。

在进行完 $m$ 次区间加法之后，正当Orange准备查询一次全局最大值时，他惊奇的发现自己写的线段树存在bug，他的前 $m$ 次区间加法有一个失效了，从而导致他的这次查询不一定能得到正确答案，而Orange并不知道是哪一次区间加法失效。

现在，Orange想知道，在存在一次失效加法的前提下，Orange查询的期望是多少？由于答案可能是一个分数，因此请你输出答案 $\bmod 998244353$。

分数取mod表达了如下含义：假设实际答案为 $\frac{p}{q}$，你的答案 $\text{ans}$ 应该满足 $\text{ans} \times q \equiv p \pmod{998244353}$。

输入格式

输入包含多组测试数据。 对于每组测试数据： 第一行包含两个整数 $n, m$，表示线段树维护的序列长度和区间加法个数。 第二行为 $n$ 个整数 $a_i$，表示原序列。 接下来 $m$ 行，每行三个整数 $l,r,v$，表示将 $a[l,...,r]$ 的每个数都加 $v$，即一次区间加法操作。

数据范围

$n,m \le 5\times 10^5$ $a_i,v \le 10^9$

输出格式

对于每组测试数据，输出一个整数表示答案。

样例 #1

样例输入 #1

1
3 3
1 1 1
1 1 2
2 2 3
3 3 4

样例输出 #1

665496240

提示

原始序列为: $[1, 1, 1]$ 若第1次区间加法失效：$[1,4,5]$，最大值为 $5$ 若第2次区间加法失效：$[3,1,5]$，最大值为 $5$ 若第3次区间加法失效：$[3,4,1]$，最大值为 $4$ 因此最大值的期望为 $\frac{5+5+4}{3}$，对 $998244353 \bmod$ 之后为 $665496240$