Description

It was a competition lasting $n$ days. Each day, Gnar must take an exam. Due to many factors, on day $i$ Gnar’s theoretical maximum score is $a_i$, and his actual score on that day is an uniformly random integer in $[0, a_i]$ (for example, not enough time, losing points on easy problems, etc.). After $n$ days, the organizers will settle the total score and set a cutoff line. Only those whose total score is at least the cutoff line can advance.

Countless “why” filled his mind, as if every day had flaws in performance. “Flaws... if only I could rewrite past regrets...”

Late at night, Gnar began $q$ rounds of daydreaming. In each daydream, Gnar returns to day $p$ of the competition and takes the exam in a different condition, making that day’s score an uniformly random integer in $[0, x]$, while the other $n-1$ days are still random in $[0, a_i]$. However, some subtle effects cause the cutoff line to become $y$. Would his chance of advancing really be higher than in reality?

For each daydream, compute the probability of advancing modulo $998244353$. It is easy to prove that the answer can be written as an irreducible fraction $\frac{Q}{P}$. You should output the smallest non-negative integer $R$ such that $R \cdot P \equiv Q \pmod{998244353}$.

After all, it is only a daydream. Returning to day $p$ with a new maximum score $x$ will not change the real value of $a_p$. The only thing that grows is regret for youth.

Input Format

The first line contains two positive integers $n$ and $q$, representing the number of days and the number of daydreams.

The second line contains $n$ integers $a_1,a_2, \ldots ,a_n$, representing the maximum score each day in reality.

The next $q$ lines each contain three integers $p,x,y$, representing the day returned to in this daydream, the new maximum score, and the new cutoff line.

Output Format

Output $q$ lines. Each line contains one integer, the probability of advancing in the corresponding daydream modulo $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

Hint

Sample Explanation #1

In the first daydream, Gnar returns to the first day. The scores over the two days are generated uniformly at random among $\{0,0\}$, $\{0,1\}$, $\{1,0\}$, $\{1,1\}$, $\{2,0\}$, $\{2,1\}$. Only the last three cases can advance, so the answer is $\frac{1}{2}$.

In the second daydream, Gnar returns to the second day, and his condition becomes worse. Even if he gets the maximum score for both days, he still cannot advance.

Constraints and Notes

This problem uses bundled testdata. You must pass all test points in a Subtask to receive the score for that 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): no special constraints.

For all testdata, it is guaranteed that $1 \le n,q \le 10^5$, $1 \le p \le n$, $0 \le a_i,x,y \le 10^5$.

Translated by ChatGPT 5