Electi Lamps
一条街道上有 N 盏灯,第 i 盏灯位于 Xi,功率为 Pi。开灯后,它照亮闭区间 [Xi−Pi,Xi+Pi]。初始状态为 Ti:1 表示亮着,0 表示熄灭。已知 X1<X2<⋯<XN。
对每个 1≤i<N,独立考虑以下过程:
- 位于 Xi 之前的所有灯均被摧毁,不再存在。
- 如果第 i 盏灯原本熄灭,先将其打开。
- 你从 Xi 出发,最终到达 XN,并使除第 N 盏灯以外的所有灯均熄灭。
你可以在走到一盏灯所在位置时开灯或关灯,整个行走过程中只能经过被亮着的灯照亮的位置。开关灯本身不增加行走距离。
令 F(i) 为完成上述过程的最小行走总距离;若无法完成,则 F(i)=0。求
i=1∑N−1F(i)(mod998244353).
当 N=1 时,上式为空和,答案为 0。
输入格式
第一行一个整数 T,表示测试用例数。
每组数据第一行一个整数 N;接下来 N 行,每行三个整数 Xi,Pi,Ti。
输出格式
每组数据输出一行一个整数,表示所求的和对 998244353 取模的结果。
数据范围
1≤T≤103,1≤N≤106,1≤Xi,Pi≤1012,Ti∈{0,1},且 Xi<Xi+1。
所有测试用例的 N 之和不超过 106。
样例
2
3
3 1 0
5 2 0
6 2 1
3
1 8 1
4 7 1
6 1 0
8
0