There is a weighted undirected graph of \(n\) nodes which are labeled from 0 to \(n1\). 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_{k1}\) and let \(f(G_i)\) be the sum of weights of the minimum spanning tree of \(G_i\).
Find \(\sum_{i=0}^{k1} f(G_i) \) modulo 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   
The first line contains three nonnegative 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 one nonnegative integer, the answer modulo 998244353.
Sample Input 1  Sample Output 1 
13 2 3

177

Sample Input 2  Sample Output 2 
80 5 10

512

Subtask  Score 

1  4 
2  8 
3  6 
4  18 
5  12 
6  12 
7  12 
8  10 
9  18 
10  0 