有一張 $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$ 取模後的結果。

範例

輸入格式 1

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

輸出格式 1

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

輸出格式 2

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)：無特殊限制。