青春有悔

岁月奔波，已值青年的 Gnar 踏上了梦想与未来的征途。 他终失败而归。

那是一次持续 $n$ 天的角逐，每天 Gnar 必须参加一场考试，受诸多因素影响第 $i$ 天 Gnar 理论得分上限为 $a_i$，实际他当天考试的得分为 $[0, a_i]$ 中**等概率随机的整数**（因时间不够、简单题丢分等）。$n$ 天后，官方将结算总分，并划定分数线，总分达到**分数线及以上**者方可入围。 无数个“凭什么”横生于脑海，似乎每天都有发挥的缺陷。“缺陷……要是能改写过往的遗憾……” 深夜，Gnar 开始了 $q$ 次幻想。每次幻想中 Gnar 重返了角逐的第 $p$ 天，以不同的状态参加考试，使当天得分变为 $[0,x]$ 中**等概率随机的整数**，其余 $n-1$ 天依旧在 $[0,a_i]$ 中随机。然而一些微妙的效应导致分数线变为了 $y$，入围的机会真能如所料高于现实吗？ 请你求出每次幻想中的入围概率对 $998244353$ 取模的结果。容易证明答案可以表示为最简分数 $\frac{Q}{P}$，你输出的 $R$ 即满足 $R \cdot P \equiv Q \pmod{998244353}$ 的最小非负整数。 毕竟幻想，重返第 $p$ 天新的得分上限 $x$ 并不会改变现实 $a_p$ 的值，唯一萌生的只有对青春的悔恨。

第一行包含两个正整数 $n$ 和 $q$，分别为天数和幻想次数。 第二行包含 $n$ 个整数 $a_1,a_2, \ldots ,a_n$，表示现实中每天的得分上限。 接下来$q$行，每行包含三个整数 $p,x,y$，分别为该次幻想的重返日期，新的得分上限以及新的分数线。

输出 $q$ 行，每行一个整数，对应每次幻想中的入围概率对 $998244353$ 取模的结果。

2 2
1 1
1 2 2
2 0 2

499122177
0

5 3
12 16 3 15 9
1 13 25
3 10 30
4 11 17

743774619
107297923
234909256

**【样例解释 #1】** 第一次幻想，Gnar 重返了第一天，两天分别的得分情况在 $\{0,0\}$，$\{0,1\}$，$\{1,0\}$，$\{1,1\}$，$\{2,0\}$，$\{2,1\}$ 内等概率产生，其中只有后三种能够入围，故答案为 $\frac{1}{2}$。 第二次幻想，Gnar 重返了第二天，状态反而变差，即使拿满两天的得分上限也没机会入围。 ---- **【数据规模与约定】** **本题采用捆绑测试**。你必须通过 Subtask 中所有的测试点才能获得该 Subtask 的分数。 - Subtask #1 (10 points)：$n,q,a_i,x,y \le 100$。 - Subtask #2 (10 points)：$n,q,a_i,x,y \le 500$。 - Subtask #3 (10 points)：$a_i,x \le 1$。 - Subtask #4 (20 points)：$\sum a_i \le 10^5$。 - Subtask #5 (25 points)：$q = 1$。 - Subtask #6 (25 points)：无特殊限制。 对于所有的数据，保证 $1 \le n,q \le 10^5$，$1 \le p \le n$，$0 \le a_i,x,y \le 10^5$。