Problem Description

You are given a directed graph with $n$ vertices and $m$ edges, where the vertices are numbered from $1$ to $n$. Each edge has a positive integer weight $d_i$. In particular, $1\le d_i \le 100$.

Now define the bottleneck path value of vertex $i$ as follows: among all directed paths from vertex $1$ to vertex $i$, take the minimum edge weight on each path, and then take the maximum of these minimum values. In particular, if $i$ is not reachable from $1$, then its bottleneck path value is $0$.

There are $q$ modifications. Each modification specifies an edge and decreases its weight, and it is guaranteed that the weight is still a positive integer after the decrease.

After each modification, output the bottleneck path values of vertices $2\sim n$. Note that each modification is applied on top of all previous modifications; they are not independent.

Since the output is too large, let the bottleneck path value of vertex $i$ after a modification be $ans_i$. You only need to output $(\sum_{i=2}^n ans_i \times 2^i)\bmod 998244353$ after each modification.

Input Format

The first line contains three positive integers $n,m,q$ ($2\le n\le 1\times 10^5$，$1\le m \le 2\times 10^5$，$1\le q\le 2\times 10^5$), separated by spaces, with the meanings as described above.

The next $m$ lines each contain three positive integers $s_i,t_i,d_i$ ($1\le s_i,t_i\le n$，$s_i\neq t_i$，$1\le d_i \le 100$), separated by spaces, indicating that there is a directed edge from $s_i$ to $t_i$ with weight $d_i$. The index of this edge is $i$. It is guaranteed that there are no self-loops, but there may be multiple edges.

The next $q$ lines each contain two positive integers $x,y$ ($1\le x\le m$，$1\le y < d_x$), separated by spaces, indicating that the weight of edge $x$ is decreased by $y$, and it is guaranteed that the resulting weight is greater than $0$.

Output Format

Output $q$ lines, each containing one non-negative integer, which is the answer you computed.

3 3 4
1 2 3
2 3 4
1 3 5
3 1
3 2
1 2
2 3

44
36
20
20

Hint

After the first modification, the bottleneck path value of vertex $2$ is $3$, and the bottleneck path value of vertex $3$ is $4$.

After the second modification, the bottleneck path value of vertex $2$ is $3$, and the bottleneck path value of vertex $3$ is $3$.

After the third modification, the bottleneck path value of vertex $2$ is $1$, and the bottleneck path value of vertex $3$ is $2$.

After the fourth modification, the bottleneck path value of vertex $2$ is $1$, and the bottleneck path value of vertex $3$ is $2$.

Translated by ChatGPT 5