### 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'

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