题目描述

你有一张 $n$ 个点 $m$ 条边的有向图，点的下标为 $1\sim n$。每条边有一个正整数边权 $d_i$。特殊的，$1\le d_i \le 100$。

现在定义点 $i$ 的瓶颈路大小为：所有从点 $1$ 到点 $i$ 的有向路径中，最小边权的最大值。特殊的，若 $i$ 不能从 $1$ 出发到达，则其瓶颈路权值为 $0$。

有 $q$ 次修改，每次修改会指定一条边，将这条边的边权降低，保证降低后依然是正整数。

现在要求每次修改后，输出编号为 $2\sim n$ 的点的瓶颈路大小。注意，每次修改是在前面修改的基础上进行操作，并不是相互独立的。

由于输出数据量过于巨大，设每次修改完后点 $i$ 的瓶颈路大小为 $ans_i$，你只需要输出 $(\sum_{i=2}^n ans_i \times 2^i)\bmod 998244353$。

输入格式

第一行三个正整数 $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$) 由空格隔开，含义如题所述。

后面 $m$ 行每行两个正整数 $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$) 由空格隔开，表示存在一条 $s_i$ 到 $t_i$ 的有向边，边权为 $d_i$，这条边的编号为 $i$。保证无自环，但可能会有重边。

再后面 $q$ 行每行两个正整数 $x,y$ ($1\le x\le m$，$1\le y < d_x$) 由空格隔开，表示将编号为 $x$ 的边的权值下调 $y$，且保证下调以后大于 $0$。

输出格式

输出 $q$ 行每行一个非负整数，表示你求得的答案。

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

44
36
20
20

提示

第一次修改后，$2$ 号点的瓶颈路大小为 $3$，$3$ 号点的瓶颈路大小为 $4$。

第二次修改后，$2$ 号点的瓶颈路大小为 $3$，$3$ 号点的瓶颈路大小为 $3$。

第三次修改后，$2$ 号点的瓶颈路大小为 $1$，$3$ 号点的瓶颈路大小为 $2$。

第四次修改后，$2$ 号点的瓶颈路大小为 $1$，$3$ 号点的瓶颈路大小为 $2$。