Элитные лампы

Для каждой лампы $i \ (1 \leq i < N)$ необходимо определить значение $F(i)$, которое представляет собой минимальное общее расстояние, которое необходимо пройти, чтобы достичь следующего:

• Все лампы перед позицией $X_i$ считаются уничтоженными и не существуют.
• Если $i$-я лампа изначально была выключена, она включается.
• Вы начинаете на позиции $X_i$ и хотите дойти до позиции $X_N$. По пути вы должны выключить каждую лампу, кроме лампы на позиции $X_N$.

Если вы не можете достичь позиции $X_N$, обеспечивая при этом, чтобы все лампы, кроме лампы $N$, были выключены, то $F(i) = 0$.

Задача состоит в том, чтобы вычислить сумму $F(i)$ для всех $i \ (1 \leq i < N)$ по модулю $998244353$.

Примечание: Вы можете ходить только по территориям, освещенным лампами.

Формат Ввода

Первая строка содержит одно целое число $T$ ($1 \leq T \leq 10^3$) --- количество наборов входных данных.

Затем для каждого набора входных данных:

• Первая строка содержит одно целое число $N$ ($1 \leq N \leq 5 \cdot 10^5$).
• Затем следуют $N$ строк. В $i$-й из этих строк находятся три целых числа, разделенных пробелом: $X_i$, $P_i$ и $T_i$ $(1 \leq X_i \leq 10^{12}, 1 \leq P_i \leq 10^{12}, T_i \in \{0, 1\})$. -Гарантируется, что $X_i < X_{i+1}$ для всех $1 \leq i < N$.

Общая сумма $N$ по всем наборам входных данных не превышает $6 \cdot 10^5$.

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

Формат Вывода

Для каждого теста выведите одну строку, состоящую из одного целого числа --- ответа.

Система оценки

Пусть $S_N$ — общая сумма $N$ по всем наборам входных данных.