Se tiene un grafo no dirigido con $n$ vértices y pesos en las aristas, donde los nodos están numerados como $\{0, 1, \cdots, n - 1\}$. Inicialmente, hay $b$ aristas, donde la $i$-ésima arista conecta $u_i$ y $v_i$ con un peso de $w_i$.

A continuación, se realizan $a$ operaciones de forma secuencial. En la $i$-ésima operación, se añade una arista con peso $x_i$ entre cada par de nodos cuya diferencia de numeración sea exactamente $d_i$.

Sea $G$ el grafo resultante, y sean $G_0, G_1, \cdots, G_{k-1}$ sus componentes conexas. Sea $f(G_i)$ el peso total de las aristas del árbol de expansión mínima (MST) de $G_i$. Calcule $\sum_{i=0}^{k-1} f(G_i)$.

La respuesta debe darse módulo $998244353$.

Entrada

La primera línea contiene tres enteros no negativos $n, a, b$.

Las siguientes $a$ líneas contienen cada una dos enteros no negativos $d_i, x_i$ ($i = 1, 2, \cdots, a$).

Las siguientes $b$ líneas contienen cada una tres enteros no negativos $u_i, v_i, w_i$ ($i = 1, 2, \cdots, b$).

Salida

Una única línea con un entero no negativo que representa la respuesta módulo $998244353$.

Ejemplos

Entrada 1

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

Salida 1

177

Entrada 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

Salida 2

512

Entrada 3

(input data)

Salida 3

(output data)

Entrada 4

(input data)

Salida 4

(output data)

Subtareas

Para todos los casos de prueba: $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$).

Restricción especial A: Todos los $x_i$ y $w_i$ son iguales a $1$.

• Subtarea 1 ($4$ pts): $n \leq 2 \times 10^5, a \leq 10$.

• Subtarea 2 ($8$ pts): $n \leq 2 \times 10^5$.

• Subtarea 3 ($6$ pts): $a = 2, b = 0$.

• Subtarea 4 ($18$ pts): $a = 2, b \leq 5 \times 10^4$.

• Subtarea 5 ($12$ pts): $a \leq 1000, b = 0$, cumple con la restricción especial A.

• Subtarea 6 ($12$ pts): $a \leq 1000, b \leq 200$.

• Subtarea 7 ($12$ pts): $b = 0$.

• Subtarea 8 ($10$ pts): Cumple con la restricción especial A.

• Subtarea 9 ($18$ pts): Sin restricciones especiales.

(Nota: El autor del problema descubrió posteriormente que los datos de las subtareas 5 y 8 tienen propiedades especiales extrañas, por lo que se sugiere a los participantes intentar resolverlas mediante enfoques alternativos).