P10323 Rationality

The goodness of mathematics, the fundamental principle that rules the universe — rationality. **** “Light of Rationality” Io is an ancient elf graphic spellcaster. Even at a thousand years old, she can always make the best decisions rationally, without being disturbed by emotions.

Update during the contest: Note that for a fixed set of $v_1,\cdots,v_n$, the minimum value of $\text{RSS}$ can always be computed. **It is a random variable depending on the random variables $v_1,\cdots,v_n**. Denote it by $X$, and what is required is $\mathbb E[X]$. Typo fix: The English abbreviation for the residual sum of squares is $\text{RSS}$. **** Io’s thoughts returned to a great battle a thousand years ago. She remembers that there were $n$ enemies in that battle. The $i$-th enemy was at a distance $d_i$ from her (all $d_i$ are distinct). Each enemy carried a **positive integer** label $v_i$. As long as it is hit with **exactly** attack power $v_i$, it can be eliminated. She only needs to set a linear function $f(x)=ax+b$, and she can release attack power $f(d_i)$ at distance $d_i$. Fortunately, her teammates will assist with the attacks, so she only needs to choose $a,b$ to make the effect of $f(x)$ optimal, i.e., minimize $\text{RSS}$ (residual sum of squares): $$\text{RSS}=\sum_{i=1}^n(f(d_i)-v_i)^2$$ Of course, this is only her memory. She can clearly remember each distance $d_i$, but for $v_i$ she only remembers that it satisfies $l_i\leq v_i \leq r_i$. She wants to know, assuming each $v_i$ is **uniformly random** within $[l_i,r_i]$, the **expected value of the “minimum value of $\text{RSS}$”**. It can be proven that the answer is always a rational number. You only need to output the result modulo $998244353$.

The first line contains a positive integer $n$, denoting the number of enemies. The next $n$ lines each contain three positive integers $d_i,l_i,r_i$, denoting the distance from Io to the $i$-th enemy, and the lower and upper bounds of its label $v_i$. To make computation easier, Io guarantees that $d_i< d_{i+1}$ ($1\leq i

Output one integer in a single line, denoting the expected value of the minimum $\text{RSS}$ over all cases.

[Sample $1$ Explanation] In this sample, $l_i=r_i$, so the case is fully determined, and you only need to find the optimal $a,b$. It is easy to see that the three data points $(1,4),(3,7),(5,10)$ can be perfectly fitted by a linear function, i.e., $f(x)=\dfrac 32 x+\dfrac{5}{2}$. The deviation at each point is $0$, so the expected minimum $\text{RSS}$, i.e., the answer, is $0$. [Sample $2$ Explanation] Here we also have $l_i=r_i$. The data $(d_i,v_i)$ for the $5$ enemies are $(1,4),(2,5),(3,7),(4,8),(9,8)$. It can be proven that choosing $$a=\frac{87}{194} \ , \ b=\frac{911}{194}$$ gives a solution that minimizes $\text{RSS}$. Substituting and computing, $$\text{RSS}=\sum_{i=1}^n\left( \frac{87}{194}d_i+\frac{911}{194}-v_i\right)^2=\frac{1047}{194}$$ Modulo $998244353$, the answer is $488831003$. [Constraints] **This problem uses bundled testdata.** Subtask 1 (10 pts): $n \leq 3$. Subtask 2 (10 pts): $l_i=r_i$. Subtask 3 (15 pts): $n\le500$, $r_i\leq 500$. Subtask 4 (15 pts): $n\le 5000$. Subtask 5 (20 pts): $n\le 10^5$. Subtask 6 (30 pts): no special constraints. For all testdata, $2\le n \le 5\times 10^5$, $1\leq l_i \leq r_i \leq 10^8$, $1\leq d_i \leq 10^8$, $d_i