manymsts

Many MSTs

There is a weighted undirected graph of $n$ nodes which are labeled from 0 to $n-1$. The graph initially has $y$ edges where the $i^{th}$ edge has a weight $c_i$ and connects nodes $a_i$ and $b_i$.

$x$ operations are then performed. In the $i^{th}$ operation, for all pairs of nodes where their label differs by $d_i$ a edge of weight $w_i$ is created connecting the two nodes.

After these opertains, let the final state of the graph be $G$. Let the connected components in $G$ be $G_0,G_1,...,G_{k-1}$ and let $f(G_i)$ be the sum of weights of the minimum spanning tree of $G_i$.

Find $\sum _{i=0}^{k-1}f(G_i)$ modulo 998244353.

Limits

$1\le n\le {10}^{18}$
$1\le x,y\le 5\ast {10}^4$
$1\le d_i<n$
$0\le a_i,b_i<n$
$1\le c_i,w_i\le 998244353$

Subtasks #	Score	Constraits
1	4	$n\le 2\ast {10}^5,x\le 10$
2	8	$n\le 2\ast {10}^5$
3	6	$x=2,y=0$
4	18	$x=2,y\le 5\ast {10}^4$
5	12	$x\le 1000,y=0$ All $c_i,w_i=1$
6	12	$x\le 1000,y\le 200$
7	12	$y=0$
8	10	All $c_i,w_i=1$
9	18	-

Input format

The first line contains three non-negative integers $n,x,y$.

The next $x$ lines contains 2 integers, where the $i^{th}$ of these lines represents $d_i$ and $w_i$

The next $y$ lines contains 3 integers, where the $i^{th}$ of these lines represents $a_i$, $b_i$ and $c_i$

Output format

Output one non-negative integer, the answer modulo 998244353.

Samples

Sample Input 1	Sample Output 1
13 2 3 4 16 5 17 10 2 3 0 7 19 5 6 12	177
Sample Input 2	Sample Output 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	512