题目描述

有一张 $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$ 的最小生成树大小（边权和），求

答案对 $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$ 后的余数。

样例 1

输入

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

输出

177

样例 2

输入

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 \neq 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）：无特殊限制。