题目描述

有一张 $n$ 个点的有边权无向图，结点按 $\{0, 1, \cdots, n - 1\}$ 编号。初始时有 $b$ 条边，第 $i$ 条连接 $u_i$ 和 $v_i$，边权为 $w_i$。

接下来依次对它进行 $a$ 次操作。第 $i$ 次操作中，每对编号差为 $d_i$ 的结点之间被连了一条权为 $x_i$ 的边。

记最终得到的图为 $G$，其连通块依次为 $G_0, G_1, \cdots, G_{k-1}$。记 $f(G_i)$ 为 $G_i$ 的最小生成树大小（边权和），求 $\sum_{i=0}^{k-1} f(G_i)$。

答案对 $998244353$ 取模。

输入格式

第一行包含三个非负整数 $n, a, b$。

接下来的 $a$ 行每行包含两个非负整数 $d_i, x_i(i = 1, 2, \cdots, a)$。

接下来的 $b$ 行每行包含三个非负整数 $u_i, v_i, w_i(i = 1, 2, \cdots, b)$。

输出格式

仅一行一个非负整数，表示答案模 $998244353$ 后的余数。

13 2 3
4 16
5 17
10 2 3
0 7 19
5 6 12

177

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

512

数据范围与提示

对于所有测试点：$1 \leq n \leq 10^{18}$，$0 \leq a, b \leq 5 \times 10^4$，$1 \leq d_i < n(1 \leq i \leq a)$，$0 \leq x_i < 998244353(1 \leq i \leq a)$，$0 \leq u_i, v_i < n, u_i \not= v_i(1 \leq i \leq b)$，$0 \leq w_i < 998244353(1 \leq i \leq b)$。

特殊限制 A：所有 $x_i$ 和 $w_i$ 均为 $1$。

subtask $1$($4$ pts)：$n \leq 2 \times 10^5, a \leq 10$；

subtask $2$($8$ pts)：$n \leq 2 \times 10^5$；

subtask $3$($6$ pts)：$a = 2, b = 0$；

subtask $4$($18$ pts)：$a = 2, b \leq 5 \times 10^4$；

subtask $5$($12$ pts)：$a \leq 1000, b = 0$，满足特殊限制 A；

subtask $6$($12$ pts)：$a \leq 1000, b \leq 200$;

subtask $7$($12$ pts)：$b = 0$；

subtask $8$($10$ pts)：满足特殊限制 A；

subtask $9$($18$ pts)：无特殊限制。