题目背景

风雪飘摇落下，这白色的天地。

为了心底不可抹去的温暖啊，便让这纹路化作最后的羽翼。

直到我们再度相见，哪怕重新回到昨天。

题目描述

伊正在帮助薰完成她的阵法。薰的阵法可以视作一棵 $n$ 个节点的有根树，每个节点都有一个魔力阈值 $a$ 与魔力等级 $b$。初始时将会给出阵法的形态与薰为每个节点设定的 $a,b$ 值。

接下来，伊将会对这个阵法进行几次测试并调整一些节点的 $a,b$ 值，以使得这个阵法可以拥有足够的效率。

每一次测试时，伊都会指定一个源点 $x$ 与范围 $k$。定义本次测试消耗的能量为 $\sum\limits_{y=1}^n\mathrm{dis}(x,y)(a_x+a_y)[|b_x-b_y|\le k]$，定义 $\mathrm{dis}(x,y)$ 为 $x,y$ 两点树上最短路径的边数。

但是这个值太大了，所以伊只需要你输出结果对 $998244353$ 取模的值即可。

输入格式

第一行输入两个数 $n,m$。

接下来 $n-1$ 行，每行输入两个数 $u,v$，表示树上存在一条连接 $u,v$ 的边。

接下来 $n$ 行，第 $i$ 行输入两个数表示 $a_i,b_i$。

接下来 $m$ 行，每行输入以下格式之一：

• 1 x v，修改 $a_x$ 为 $v$。
• 2 x v，修改 $b_x$ 为 $v$。
• 3 x k，进行一次以 $x$ 为源点、范围为 $k$ 的测试，查询本次测试消耗的能量可能的最小值。

输出格式

对每次查询操作，输出一行一个数表示答案。

5 3
2 1
3 2
4 2
5 2
13 8
9 10
9 3
20 6
14 7
3 2 5
3 3 4
3 3 8

74
104 
166

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

63

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

30
30

提示

对所有数据，满足 $1\le n,m\le 10^5,1\le x\le n,1\le a,b,k\le 10^5$。

::cute-table{tuack}

子任务编号	$n,m\le$	特殊性质	分值
#1	$2000$	无	$\text{5pts}$
#2	$5\times 10^4$	^	$\text{20pts}$
#3	$10^5$	AB	$\text{5pts}$
#4	^	B	$\text{10pts}$
#5		C
#6		无	$\text{50pts}$

特殊性质 A：不存在 $1$ 操作。

特殊性质 B：不存在 $2$ 操作。

特殊性质 C：保证任意时刻 $b_i \le 3$。