Soit un graphe non orienté pondéré à $n$ sommets, numérotés $\{0, 1, \cdots, n - 1\}$. Initialement, il y a $b$ arêtes, où la $i$-ième arête relie $u_i$ et $v_i$ avec un poids $w_i$.

Ensuite, on effectue successivement $a$ opérations. Lors de la $i$-ième opération, une arête de poids $x_i$ est ajoutée entre chaque paire de sommets dont la différence de numéro est égale à $d_i$.

Soit $G$ le graphe final obtenu, et $G_0, G_1, \cdots, G_{k-1}$ ses composantes connexes. Soit $f(G_i)$ la taille de l'arbre couvrant minimal (la somme des poids des arêtes) de $G_i$. Calculez $\sum_{i=0}^{k-1} f(G_i)$.

La réponse doit être donnée modulo $998244353$.

Entrée

La première ligne contient trois entiers non négatifs $n, a, b$.

Les $a$ lignes suivantes contiennent chacune deux entiers non négatifs $d_i, x_i$ ($i = 1, 2, \cdots, a$).

Les $b$ lignes suivantes contiennent chacune trois entiers non négatifs $u_i, v_i, w_i$ ($i = 1, 2, \cdots, b$).

Sortie

Une seule ligne contenant un entier non négatif, représentant la réponse modulo $998244353$.

Exemples

Entrée 1

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

Sortie 1

177

Entrée 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

Sortie 2

512

Remarque

Les exemples 3 et 4 sont fournis dans les fichiers joints.

Contraintes

Pour tous les cas de test : $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$).

Restriction spéciale A : tous les $x_i$ et $w_i$ sont égaux à $1$.

• Sous-tâche 1 (4 pts) : $n \leq 2 \times 10^5, a \leq 10$ ;
• Sous-tâche 2 (8 pts) : $n \leq 2 \times 10^5$ ;
• Sous-tâche 3 (6 pts) : $a = 2, b = 0$ ;
• Sous-tâche 4 (18 pts) : $a = 2, b \leq 5 \times 10^4$ ;
• Sous-tâche 5 (12 pts) : $a \leq 1000, b = 0$, satisfait la restriction spéciale A ;
• Sous-tâche 6 (12 pts) : $a \leq 1000, b \leq 200$ ;
• Sous-tâche 7 (12 pts) : $b = 0$ ;
• Sous-tâche 8 (10 pts) : satisfait la restriction spéciale A ;
• Sous-tâche 9 (18 pts) : aucune restriction spéciale.

(Note : l'auteur du problème a découvert après coup que les données des sous-tâches 5 et 8 possèdent des propriétés spéciales étranges ; il est donc conseillé aux participants d'essayer d'utiliser des programmes originaux pour résoudre les sous-tâches 5 et 8.)