Dana jest graf nieskierowany o $n$ wierzchołkach z wagami krawędzi. Wierzchołki są ponumerowane od $\{0, 1, \cdots, n - 1\}$. Początkowo istnieje $b$ krawędzi, gdzie $i$-ta krawędź łączy $u_i$ oraz $v_i$ i ma wagę $w_i$.

Następnie wykonujemy kolejno $a$ operacji. W $i$-tej operacji, każda para wierzchołków, których różnica numerów wynosi $d_i$, zostaje połączona krawędzią o wadze $x_i$.

Niech $G$ będzie grafem końcowym, a $G_0, G_1, \cdots, G_{k-1}$ jego składowymi spójnymi. Niech $f(G_i)$ oznacza wagę minimalnego drzewa rozpinającego (MST) składowej $G_i$. Oblicz $\sum_{i=0}^{k-1} f(G_i)$.

Wynik należy podać modulo $998244353$.

Wejście

Pierwsza linia zawiera trzy nieujemne liczby całkowite $n, a, b$.

Kolejne $a$ linii zawiera po dwie nieujemne liczby całkowite $d_i, x_i$ ($i = 1, 2, \cdots, a$).

Kolejne $b$ linii zawiera po trzy nieujemne liczby całkowite $u_i, v_i, w_i$ ($i = 1, 2, \cdots, b$).

Wyjście

Jedna linia zawierająca jedną nieujemną liczbę całkowitą, będącą wynikiem operacji modulo $998244353$.

Przykład

Wejście 1

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

Wyjście 1

177

Wejście 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

Wyjście 2

512

Podzadania

Dla wszystkich przypadków testowych: $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$).

Ograniczenie specjalne A: wszystkie $x_i$ oraz $w_i$ są równe $1$.

• Podzadanie 1 (4 pkt): $n \leq 2 \times 10^5, a \leq 10$
• Podzadanie 2 (8 pkt): $n \leq 2 \times 10^5$
• Podzadanie 3 (6 pkt): $a = 2, b = 0$
• Podzadanie 4 (18 pkt): $a = 2, b \leq 5 \times 10^4$
• Podzadanie 5 (12 pkt): $a \leq 1000, b = 0$, spełnione ograniczenie specjalne A
• Podzadanie 6 (12 pkt): $a \leq 1000, b \leq 200$
• Podzadanie 7 (12 pkt): $b = 0$
• Podzadanie 8 (10 pkt): spełnione ograniczenie specjalne A
• Podzadanie 9 (18 pkt): brak ograniczeń specjalnych

(Uwaga: autorzy zadania odkryli po fakcie, że dane w podzadaniach 5 i 8 mają specyficzne właściwości, dlatego zaleca się zawodnikom samodzielne próby rozwiązania tych podzadań za pomocą niestandardowych podejść.)