You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

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