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

Submitting .cpp to 'manymsts'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 4 Seconds
Memory Limit: 1024MB
No. of ACs: 1
Your best score: 0
Source: LOJ #3635

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