题目描述

红魔馆的内部形态是一棵树，总共有 $n$ 个房间，其中它们由 $n-1$ 个走廊连接。

每条走廊都有一个难走程度 $w$ 。

每一天，十六夜咲夜都会打扫房间。

她在打扫房间的时候会使用能力，暂停时间。所以打扫一个房间不要任何时间。然而进过一个走廊是要花费时间的，所话花费的时间就是这个走廊的难走程度。

现在给出 $m$ 个特殊房间，把这些房间记为集合 $A$ 。现在十六夜咲夜想随机的从一个房间开始打扫，然后随机进入另一个 $A$ 中没有被打扫的房间去打扫它，直到把这 $m$ 个房间都打扫干净。

现在，她想知道她把这些房间打扫干净的期望时间对 $998244353$ 取模的值。

换句话说，设 $d(x,y)$ 表示从树上点 $x$ 到 $y$ 的边权和。

将 $A$ 随机打乱得到序列 $a$ 。

求 $\sum\limits_{i=2}^m d(a_{i-1},a_i) \ \ \ \ \ \bmod 998244353$ 。的期望值

但是每天早上，帕秋莉会在某一个房间 $x$ 使用魔法，魔法有一个强度 $k$ 。这会使得所有与 $x$ 相连的走廊的难走程度增加 $k$。（十六夜咲夜：谢谢你啊。）

而你需要回答每天使用魔法后的期望值。

输入格式

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

接下来 $n$ 行，每行三个整数 $u,v,w$，表示 $u$ 到 $v$ 有一条难走程度为 $w$ 的边。

接着一行 $m$ 个整数，表示 $m$ 个特殊房间。

然后输入 $q$，表示询问个数。

$q$ 行，每行两个整数 $x,k$，表示在点 $x$ 使用强度为 $k$ 的魔法。

输出格式

$q$ 行，表示每次修改后的期望值。

样例 #1

样例输入 #1

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

样例输出 #1

8
332748127
665496258

提示

测试点编号	特殊限制	分值
$1\sim 4$	$1\le n,q\le 10$	$20$
$5\sim 6$	$1\le n,q\le 100$	$10$
$7\sim 10$	$q=1$	$20$
$11\sim 12$	$m=3$	$10$
$13\sim 14$	修改操作只在叶子上
$15\sim 20$	无	$30$

对于 $100\%$ 的数据：

• $1 \le n\le 5\times 10^5,m\le n,1 \le q \le5\times 10^5$。

• $1 \le w,k \le 10^9$ 。

对于样例中的第一个询问，$a$ 有 2 3 4,2 4 3,3 2 4,3 4 2,4 2 3,4 3 2这 $6$ 种可能，它们的值分别为 $6,9,9,9,9,6$，所以期望为 $\dfrac{6+9+9+9+9+6}{6}=8$