P7111 Youth Has Regrets

Time has rushed by. Gnar, now at the age of youth, set out on a journey toward dreams and the future. In the end, he returned in failure.

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.

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

**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