#P18062. Electi Lamps

Electi Lamps

Electi Lamps

一条街道上有 NN 盏灯,第 ii 盏灯位于 XiX_i,功率为 PiP_i。开灯后,它照亮闭区间 [Xi−Pi,Xi+Pi][X_i-P_i,X_i+P_i]。初始状态为 TiT_i:11 表示亮着,00 表示熄灭。已知 X1<X2<⋯<XNX_1<X_2<\cdots<X_N。

对每个 1≤i<N1\le i<N,独立考虑以下过程:

  • 位于 XiX_i 之前的所有灯均被摧毁,不再存在。
  • 如果第 ii 盏灯原本熄灭,先将其打开。
  • 你从 XiX_i 出发,最终到达 XNX_N,并使除第 NN 盏灯以外的所有灯均熄灭。

你可以在走到一盏灯所在位置时开灯或关灯,整个行走过程中只能经过被亮着的灯照亮的位置。开关灯本身不增加行走距离。

令 F(i)F(i) 为完成上述过程的最小行走总距离;若无法完成,则 F(i)=0F(i)=0。求

∑i=1N−1F(i)(mod998244353).\sum_{i=1}^{N-1} F(i)\pmod{998244353}.

当 N=1N=1 时,上式为空和,答案为 00。

输入格式

第一行一个整数 TT,表示测试用例数。

每组数据第一行一个整数 NN;接下来 NN 行,每行三个整数 Xi,Pi,TiX_i,P_i,T_i。

输出格式

每组数据输出一行一个整数,表示所求的和对 998244353998244353 取模的结果。

数据范围

1≤T≤1031\le T\le10^3,1≤N≤1061\le N\le10^6,1≤Xi,Pi≤10121\le X_i,P_i\le10^{12},Ti∈{0,1}T_i\in\{0,1\},且 Xi<Xi+1X_i<X_{i+1}。

所有测试用例的 NN 之和不超过 10610^6。

样例

2
3
3 1 0
5 2 0
6 2 1
3
1 8 1
4 7 1
6 1 0
8
0