题目描述

你有两棵树 $T$ 和 $G$，$T$ 中的点编号为 $1\sim n$，初始时给定 $T$。初始时 $G$ 也有 $n$ 个点，编号为 $(1,1)\sim (1,n)$，其中 $(1,i),(1,j)$ 之间有边当且仅当 $T$ 中 $i,j$ 之间有边。

有 $q$ 次操作，第 $k$ 次操作给定 $x,y,z$，表示对 $G$ 进行如下修改：

• 新建 $n$ 个结点，编号为 $(k+1,1)\sim (k+1,n)$；
• 对于 $T$ 中每条边 $(i,j)$，在 $G$ 中 $(k+1,i),(k+1,j)$ 之间连一条边；
• 在 $G$ 中 $(x,y)$ 和 $(k+1,z)$ 之间连一条边。

不难发现，这样得到的 $G$ 仍为一棵树。

请在每次修改后，求出 $G$ 中所有无序点对之间的最短距离之和，这里认为每条边的长度都是 $1$。答案可能很大，你只需要求出它对 $998244353$ 取模的值。

部分测试点强制在线。

输入格式

第一行三个非负整数 $n,q,type$，$type$ 表示该测试点是否强制在线。

接下来 $n-1$ 行，每行两个正整数 $x,y$，表示 $T$ 中有一条边 $(x,y)$。

接下来 $q$ 行，每行三个正整数 $x,y,z$，表示一次操作。设上一次操作后的答案为 $ans$（第一次操作前答案为 $0$），则真实的 $x,y,z$ 均应异或上 $ans\times type$。

输出格式

输出 $q$ 行，第 $i$ 行为第 $i$ 次操作后，$G$ 中所有无序点对之间的最短距离之和模 $998244353$ 的值。

样例

样例输入 1

5 13 0
1 2
1 3
2 4
2 5
1 3 2
1 2 4
2 3 4
1 2 4
2 2 4
1 3 3
1 4 4
2 5 5
1 2 1
1 2 1
4 3 4
1 4 5
6 5 4

样例输出 1

131
404
972
1630
2463
3456
4799
6342
7815
9398
12696
15094
18377

样例输入 2

5 13 1
1 2
1 3
2 4
2 5
1 3 2
130 129 135
406 407 400
973 974 968
1628 1628 1626
2462 2460 2460
3457 3460 3460
4797 4794 4794
6343 6340 6343
7814 7813 7814
9394 9397 9394
12697 12700 12701
15088 15091 15090

样例输出 2

131
404
972
1630
2463
3456
4799
6342
7815
9398
12696
15094
18377

样例 2 解释

该样例是样例 1 的强制在线版本。

数据范围

本题捆绑测试。 对于所有数据，$1\le n,q\le 5\times 10^4$，$type \in \{0,1\}$，保证每次操作都合法。详细数据范围如下：