有一张 n 个点的有边权无向图,结点按 {0,1,⋯,n−1} 编号。初始时有 b 条边,第 i 条连接 ui 和 vi,边权为 wi。
接下来依次对它进行 a 次操作。第 i 次操作中,每对编号差为 di 的结点之间被连了一条权为 xi 的边。
记最终得到的图为 G,其连通块依次为 G0,G1,⋯,Gk−1。记 f(Gi) 为 Gi 的最小生成树大小(边权和),求 ∑k−1i=0f(Gi)。
答案对 998244353 取模。
输入格式
第一行包含三个非负整数 n,a,b。
接下来的 a 行每行包含两个非负整数 di,xi(i=1,2,⋯,a)。
接下来的 b 行每行包含三个非负整数 ui,vi,wi(i=1,2,⋯,b)。
输出格式
仅一行一个非负整数,表示答案模 998244353 后的余数。
样例一
input
13 2 3
4 16
5 17
10 2 3
0 7 19
5 6 12
output
177
样例二
input
80 5 10
35 5
68 7
4 11
67 15
21 18
1 20 13
33 48 5
37 68 16
64 72 4
22 11 13
73 17 1
24 71 9
71 30 9
16 18 2
13 2 4
output
512
样例三、样例四
见下发文件。
子任务
对于所有测试点:1≤n≤1018,0≤a,b≤5×104,1≤di<n(1≤i≤a),0≤xi<998244353(1≤i≤a),0≤ui,vi<n,ui≠vi(1≤i≤b),0≤wi<998244353(1≤i≤b)。
特殊限制 A:所有 xi 和 wi 均为 1。
subtask 1(4 pts):n≤2×105,a≤10;
subtask 2(8 pts):n≤2×105;
subtask 3(6 pts):a=2,b=0;
subtask 4(18 pts):a=2,b≤5×104;
subtask 5(12 pts):a≤1000,b=0,满足特殊限制 A;
subtask 6(12 pts):a≤1000,b≤200;
subtask 7(12 pts):b=0;
subtask 8(10 pts):满足特殊限制 A;
subtask 9(18 pts):无特殊限制。
时间限制:3s
空间限制:512MB
(注:出题人事后发现 subtask 5 和 8 的数据具有奇怪的的特殊性质,故这里建议选手自行尝试使用奇怪的程序通过 subtask 5 和 8。)