$n$ 個の頂点を持つ重み付き無向グラフがある。頂点には $\{0, 1, \cdots, 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$ で割った余りを出力せよ。

入力形式

1 行目に 3 つの非負整数 $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 行で出力せよ。

入出力例

入力 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 \not= v_i (1 \leq i \leq b)$、$0 \leq w_i < 998244353 (1 \leq i \leq b)$ を満たす。

特殊制限 A：すべての $x_i$ および $w_i$ は $1$ である。

• subtask 1 (4 点)：$n \leq 2 \times 10^5, a \leq 10$
• subtask 2 (8 点)：$n \leq 2 \times 10^5$
• subtask 3 (6 点)：$a = 2, b = 0$
• subtask 4 (18 点)：$a = 2, b \leq 5 \times 10^4$
• subtask 5 (12 点)：$a \leq 1000, b = 0$、特殊制限 A を満たす
• subtask 6 (12 点)：$a \leq 1000, b \leq 200$
• subtask 7 (12 点)：$b = 0$
• subtask 8 (10 点)：特殊制限 A を満たす
• subtask 9 (18 点)：特殊制限なし

（注：出題者は事後に subtask 5 および 8 のデータが奇妙な特殊性質を持つことを発見した。そのため、ここでは競技者が各自で工夫して subtask 5 および 8 を通過させることを推奨する。）