题目描述

小 C 是 F 国的总统，尽管这个国家仅存在于网络游戏中，但他确实是这个国家的总统。

F 国由 $n$ 个城市构成，这 $n$ 个城市之间由 $n-1$ 条双向道路互相连接。保证从任意一个城市出发，都能通过这 $n-1$ 条双向道路，到达任意一个城市。

当然，通过这些双向道路是要收费的。通过第 $i$ 条双向道路，需要花费 $c_i$ 元。我们称 $c_i$ 为第 $i$ 条双向道路的费用。

我们定义 $cost(x,y)$ 表示从城市 $x$ 到城市 $y$ 的简单路径上，所有经过的双向道路的费用之和。特殊地，当 $x=y$ 时，$cost(x,y)=0$。

为了促进 F 国发展，小 C 新建了一个城市 $n+1$。现在他需要再新建一条双向道路，使得城市 $n+1$ 也可以通过这 $n$ 条双向道路到达任意一个城市。

他共有 $q$ 个新建道路的方案，每个方案会给定两个参数 $k_i,w_i$；对于每一个方案，你需要求出在新建一条连接城市 $k_i$ 和城市 $n+1$ 且费用为 $w_i$ 的双向道路后，所有 $cost(i,j)$ 之和，即 $\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j)$。

由于答案可能很大，所以你只需要输出答案对 $998244353$ 取模的结果。

方案之间相互独立，也就是说所有方案不会影响现有的道路，这些方案不会真正被施行。

输入格式

第一行两个整数 $n,q$。

接下来 $n-1$ 行，第 $i$ 行三个整数 $u_i,v_i,c_i$，表示存在一条连接城市 $u_i$ 和城市 $v_i$ 的双向道路，其费用为 $c_i$。

接下来 $q$ 行，第 $i$ 行两个整数 $k_i,w_i$，表示一个新建道路的方案。

输出格式

共 $q$ 行，每行一个整数，第 $i$ 行的整数表示在新建一条连接城市 $k_i$ 和城市 $n+1$ 且费用为 $w_i$ 的双向道路后，所有 $cost(i,j)$ 之和对 $998244353$ 取模的结果，即 $\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j) \bmod 998244353$。

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

100
88

9 5
2 3 6
6 1 4
5 2 10
2 4 1
9 1 9
2 8 3
1 2 3
7 4 8
4 9
7 3
6 1
9 7
2 1

1050
1054
970
1148
896

提示

【样例解释 #1】

在新建一条连接城市 $1$ 和城市 $5$ 且费用为 $2$ 的双向道路后，F 国的道路如下图所示：

例如，此时 $cost(4,5)=9$，$cost(1,3)=5$。

容易求得此时 $\sum\limits_{i=1}^{n+1} \sum\limits_{j=1}^{n+1} cost(i,j)=100$。

【样例 #3】

见附加文件中的 city/city3.in 与 city/city3.ans。

该样例满足测试点 $4$ 的限制。

【样例 #4】

见附加文件中的 city/city4.in 与 city/city4.ans。

该样例满足测试点 $11$ 的限制。

【样例 #5】

见附加文件中的 city/city5.in 与 city/city5.ans。

该样例满足测试点 $14$ 的限制。

【样例 #6】

见附加文件中的 city/city6.in 与 city/city6.ans。

该样例满足测试点 $20$ 的限制。

【数据范围】

对于 $100\%$ 的数据，$2 \le n \le 2\times10^5$，$1 \le q \le 2\times10^5$，$1 \le u_i,v_i,k_i \le n$，$1 \le c_i,w_i \le 10^6$，保证从任意一个城市出发，都能通过原本存在的 $n-1$ 条双向道路，到达任意一个城市。

测试点编号	$n \le$	$q \le$	特殊性质
$1\sim3$	$80$		无
$4\sim7$	$5000$	$5000$
$8\sim10$		$2\times10^5$
$11\sim13$	$2\times10^5$		A
$14\sim16$			B
$17\sim20$			无

特殊性质 A：保证对于所有的 $1 \le i \lt n$，都有 $u_i=i,v_i=i+1$。

特殊性质 B：保证对于所有的 $1 \le i \le q$，都有 $k_i=1$。