Electi Lamps - KhIMIO

For each lamp $i \ (1 \leq i < N)$, you need to determine a value $F(i)$, which is the minimum total distance you must walk to achieve the following:

• All lamps before position $X_i$ are considered destroyed and do not exist.
• If the $i$-th lamp was initially off, it is turned on.
• You start at position $X_i$ and want to walk to position $X_N$. Along the way, you must turn off every lamp except for the one at position $X_N$.

If you cannot reach position $X_N$ while ensuring all lamps except lamp $N$ are turned off, then $F(i) = 0$.

The task is to compute the sum of $F(i)$ for all $i \ (1 \leq i < N)$, modulo $998244353$.

Note: You can only walk in areas illuminated by the lamps.

Input Format

The first line contains one integer $T$ ($1 \leq T \leq 10^3$), the number of test cases.

Then, for each test case:

• The first line contains one integer $N$ ($1 \leq N \leq 5 \cdot 10^5$).
• Then, $N$ lines follow. In the $i$-th of these lines, there are three space-separated integers $X_i$, $P_i$, and $T_i$ $(1 \leq X_i \leq 10^{12}, 1 \leq P_i \leq 10^{12}, T_i \in \{0, 1\})$.
• It is guaranteed that $X_i < X_{i+1}$ for all $1 \leq i < N$.

The total sum of $N$ across all test cases does not exceed $6 \cdot 10^5$.

Output Format

For each test, print one line consisting of one integer, the answer.

Scoring

Let $S_N$ be the total sum of $N$ across all test cases.