Дан неориентированный взвешенный граф с $n$ вершинами, пронумерованными от $0$ до $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

Примеры 3, 4

См. приложенные файлы.

Подзадачи

Для всех тестов: $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$).

Особое ограничение A: все $x_i$ и $w_i$ равны $1$.

• Подзадача 1 (4 балла): $n \leq 2 \times 10^5, a \leq 10$.
• Подзадача 2 (8 баллов): $n \leq 2 \times 10^5$.
• Подзадача 3 (6 баллов): $a = 2, b = 0$.
• Подзадача 4 (18 баллов): $a = 2, b \leq 5 \times 10^4$.
• Подзадача 5 (12 баллов): $a \leq 1000, b = 0$, выполняется особое ограничение A.
• Подзадача 6 (12 баллов): $a \leq 1000, b \leq 200$.
• Подзадача 7 (12 баллов): $b = 0$.
• Подзадача 8 (10 баллов): выполняется особое ограничение A.
• Подзадача 9 (18 баллов): без дополнительных ограничений.

(Примечание: автор задачи обнаружил, что данные в подзадачах 5 и 8 обладают странными свойствами, поэтому участникам предлагается попробовать решить их с помощью нестандартных подходов.)