Background

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.

Problem Description

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$.

Input Format

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 <n$), and also that:

$$n\sum_{i=1}^nd_i^2 \not \equiv \left(\sum_{i=1}^nd_i \right)^2 \pmod{998244353}$$

This ensures that the answer always exists modulo $998244353$.

Output Format

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

3
1 4 4
3 7 7
5 10 10

0

5
1 4 4
2 5 5
3 7 7
4 8 8
9 8 8

488831003

5
1 1 4
2 2 5
3 3 7
4 2 8
9 3 8

884183796

10
123 1 10
234 11 14
345 10 20
456 6 6
567 20 30
678 84 90
789 1 3
8910 8 15
91011 123 129
101112 56 64

483360041

Hint

[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<d_{i+1}$ ($1\leq i <n$), and:

$$n\sum_{i=1}^nd_i^2 \not \equiv \left(\sum_{i=1}^nd_i \right)^2 \pmod{998244353}$$

[Hint]

This problem asks for the expected value of the “minimum value of $\text{RSS}$”. For a discrete random variable $X$, suppose it can take values $a_1,a_2,\cdots,a_n$ with probabilities $p_1,p_2,\cdots,p_n$ ($p_1+\cdots+p_n=1$). Then its expected value is defined as:

$$\mathbb E[X]=\sum_{i=1}^np_i a_i$$

For how to compute a rational number modulo a prime, please refer to the template problem.

Translated by ChatGPT 5