题目背景

岁月奔波，已值青年的 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$。