There is an undirected graph with $n$ vertices, labeled $\{0, 1, \cdots, n - 1\}$, and weighted edges. Initially, there are $b$ edges, where the $i$-th edge connects $u_i$ and $v_i$ with weight $w_i$.
Next, $a$ operations are performed sequentially. In the $i$-th operation, an edge with weight $x_i$ is added between every pair of vertices whose indices differ by $d_i$.
Let the final graph be $G$, and let its connected components be $G_0, G_1, \cdots, G_{k-1}$. Let $f(G_i)$ be the weight of the Minimum Spanning Tree (MST) of $G_i$. Calculate $\sum_{i=0}^{k-1} f(G_i)$.
The answer should be taken modulo $998244353$.
Input
The first line contains three non-negative integers $n, a, b$.
The next $a$ lines each contain two non-negative integers $d_i, x_i$ ($i = 1, 2, \cdots, a$).
The next $b$ lines each contain three non-negative integers $u_i, v_i, w_i$ ($i = 1, 2, \cdots, b$).
Output
Output a single non-negative integer representing the answer modulo $998244353$.
Examples
Input 1
13 2 3 4 16 5 17 10 2 3 0 7 19 5 6 12
Output 1
177
Input 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
Output 2
512
Input 3
(input data)
Output 3
(output data)
Input 4
(input data)
Output 4
(output data)
Subtasks
For all test cases: $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$).
Special Constraint A: All $x_i$ and $w_i$ are $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$, satisfies Special Constraint A.
Subtask 6 (12 pts): $a \leq 1000, b \leq 200$.
Subtask 7 (12 pts): $b = 0$.
Subtask 8 (10 pts): Satisfies Special Constraint A.
Subtask 9 (18 pts): No special constraints.