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 \leq n \leq 10^{18}\)
\(1 \leq x, y \leq 5*10^4\)
\(1 \leq d_i < n\)
\(0 \leq a_i, b_i < n\)
\(1 \leq c_i, w_i \leq 998244353\)

Subtasks #	Score	Constraits
1	4	\(n \leq 2*10^5, x \leq 10\)
2	8	\(n \leq 2*10^5\)
3	6	\(x = 2, y = 0\)
4	18	\(x = 2, y \leq 5*10^4\)
5	12	\(x \leq 1000, y = 0\) All \(c_i, w_i = 1\)
6	12	\(x \leq 1000, y \leq 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