Bottleneck Path Modification

You are given a directed graph with (n) nodes and (m) edges. The nodes are numbered from (1) to (n). Each edge has a positive integer weight (d_i) satisfying (1\le d_i\le 100).

For a node (i), define its bottleneck path value as follows: among all the directed paths from node (1) to node (i), let the value of a path be the minimum edge weight along that path; then the bottleneck path value of node (i) is the maximum among these values. If node (i) is unreachable from node (1), then its bottleneck path value is (0).

There will be (q) modifications. In each modification, you are given an edge index and a new weight, and the weight of that edge is decreased (the new weight is still a positive integer). These modifications are cumulative. After each modification, for every node (i) (with (2\le i\le n)) let (ans_i) be its current bottleneck path value. You are required to output a single number per modification: [ S = \left(\sum_{i=2}^{n} ans_i \times 2^i \right) \bmod 998244353. ]

The input and output formats are described below.

inputFormat

The input is given as follows:

• The first line contains three integers (n), (m) and (q).
• The next (m) lines each contain three integers (u), (v) and (d), representing a directed edge from (u) to (v) with weight (d). Edges are numbered from (1) to (m) in the order they appear.
• The next (q) lines each contain two integers: an edge index and a new weight. This indicates that the edge's weight is decreased to the new value (the new value is guaranteed to be a positive integer and less than the current weight).

outputFormat

After each modification, output a single line containing the value of (S = \left(\sum_{i=2}^{n} ans_i \times 2^i\right) \bmod 998244353), where (ans_i) is the bottleneck path value for node (i) after that modification.

sample

3 3 2
1 2 10
2 3 5
1 3 6
2 3
3 4

88
72