Background

The fundamental principle that governs the universe — Rationality.

Iol, the ancient elven geomancer known as the "Light of Rationality," has lived for a thousand years and always makes the optimal decisions without emotional interference.

Problem Description

Update during the contest: Note that for a given set of $v_1, \cdots, v_n$, the minimum value of $\text{RSS}$ can be determined. It is a random variable with respect to the random variables $v_1, \cdots, v_n$, denoted as $X$, and the requirement is to find $\mathbb{E}[X]$.
Correction: The residual sum of squares is abbreviated as $\text{RSS}$.

Iol's thoughts return to a great battle a thousand years ago.

She remembers that in that battle, there were $n$ enemies, each at a unique distance $d_i$ from her. Each enemy had a positive integer tag $v_i$, and it could be eliminated by hitting it with exactly $v_i$ attack power.

By setting a linear function $f(x) = ax + b$, she could unleash $f(d_i)$ attack power at the distance $d_i$. Fortunately, her teammates would assist her, so she only needed to determine $a, b$ to optimize $f(x)$, i.e., to minimize the $\text{RSS}$ (residual sum of squares):
$$ \text{RSS} = \sum_{i=1}^n (f(d_i) - v_i)^2 $$
Of course, this is just her memory. She clearly remembers the distance $d_i$ to each enemy, but for $v_i$, she only remembers that it is within the range $l_i \leq v_i \leq r_i$.

She wants to know the expected value of the "minimum $\text{RSS}$" under the assumption that each $v_i$ is uniformly randomly distributed within $[l_i, r_i]$.
It can be proven that the answer is always a rational number, and you only need to tell her the result modulo $998244353$.

Input Format

The first line contains a positive integer $n$, the number of enemies.
The next $n$ lines each contain three positive integers $d_i, l_i, r_i$, representing the distance of the $i$-th enemy from Iol, and the lower and upper bounds of the tag $v_i$, respectively.

For your convenience, Iol guarantees that $d_i < d_{i+1}$ ($1 \leq i < n$), and:
$$ n \sum_{i=1}^n d_i^2 \not \equiv \left( \sum_{i=1}^n d_i \right)^2 \pmod{998244353} $$
Ensuring that the answer exists under modulo $998244353$.

Output Format

Output a single integer, the expected value of the minimum $\text{RSS}$ under all possible cases.

Sample Input and Output

Input Sample #1

3
1 4 4
3 7 7
5 10 10

Output Sample #1

0

Input Sample #2

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

Output Sample #2

488831003

Input Sample #3

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

Output Sample #3

884183796

Input Sample #4

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

Output Sample #4

483360041

Notes

Explanation of Sample 1

In this sample, $l_i = r_i$, meaning the situation is determined, and we only need to find the optimal $a, b$. It is easy to see that the data points $(1, 4), (3, 7), (5, 10)$ can be perfectly fitted by a linear function: $f(x) = \frac{3}{2}x + \frac{5}{2}$, with zero deviation for each point, hence the expected minimum $\text{RSS}$, which is the answer, is $0$.

Explanation of Sample 2

Here, $l_i = r_i$ as well. The data for the 5 enemies $(d_i, v_i)$ are $(1, 4), (2, 5), (3, 7), (4, 8), (9, 8)$. It can be proven that taking
$$ a = \frac{87}{194}, b = \frac{911}{194} $$
is a solution that minimizes $\text{RSS}$. Substituting and calculating gives
$$ \text{RSS} = \sum_{i=1}^n \left( \frac{87}{194}d_i + \frac{911}{194} - v_i \right)^2 = \frac{1047}{194} $$
The answer under modulo $998244353$ is $488831003$.

Data Range

This problem uses batched testing.

Subtask 1 (10 pts): $n \leq 3$;
Subtask 2 (10 pts): $l_i = r_i$;
Subtask 3 (15 pts): $n \leq 500, r_i \leq 500$;
Subtask 4 (15 pts): $n \leq 5000$;
Subtask 5 (20 pts): $n \leq 10^5$;
Subtask 6 (30 pts): No additional constraints.

For all data, $2 \leq n \leq 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}^n d_i^2 \not \equiv \left( \sum_{i=1}^n d_i \right)^2 \pmod{998244353} $$

Hints

The problem requires finding the expected value of the "minimum $\text{RSS}$". For a discrete random variable $X$, assuming it can take values $a_1, a_2, \cdots, a_n$ with corresponding probabilities $p_1, p_2, \cdots, p_n$ ($p_1 + \cdots + p_n = 1$), its expected value can be defined as:
$$ \mathbb{E}[X] = \sum_{i=1}^n p_i a_i $$
For methods of computing rational numbers modulo, please refer to the template problem.

见题面 Input 部分

见题面 Output 部分