桃树 (4s, 512M)

你有一棵 $n$ 个点的桃树，桃树的根节点为 $1$，树上每个节点都有一个桃子，树上每条边的长度都为 $1$，节点 $u$ 上的桃子的重量为 $x_u$，树上两点的距离为这两点中唯一简单路径的边长之和。

在接下来的 $Q$ 天内，每天你都将做以下 $4$ 种操作之一：

• 操作 $1$：选择一个节点 $u$，测量 $u$ 上的桃子的重量。注意，你不会将桃子摘下，测量完后 $u$ 上的桃子重量保持不变。
• 操作 $2$：选择一个节点 $u$ 和三个非负整数 $k,c,d$，对与 $u$ 距离 $\le k$ 的所有节点上的桃子施加魔法。具体而言，对于所有 $v$ 满足 $u,v$ 在树上的距离 $\le k$，将 $x_v$ 变为 $x_v\times c+d$。
• 操作 $3$：选择一个节点 $u$ 和两个非负整数 $c,d$，对 $u$ 子树内的所有节点上的桃子施加魔法。具体而言，对于所有 $v$ 满足 $v$ 在 $u$ 的子树中，将 $x_v$ 变为 $x_v\times c+d$。
• 操作 $4$：选择两个节点 $u,v$ 和两个非负整数 $c,d$，对 $u,v$ 最短路径上的所有节点上的桃子施加魔法。具体而言，对于所有 $w$ 满足 $w$ 在 $u,v$ 的最短路径上（包含 $u,v$），将 $x_v$ 变成 $x_v\times c+d$

对于每次操作 $1$，输出你测量的结果。

输入格式

第一行两个正整数 $n,Q$。

后面 $n-1$ 行每行两个正整数表示一条树边 $(u,v)$。

后面一行 $n$ 个非负整数依次表示 $x_i$。

后面 $Q$ 行每行表示一天的操作，有如下四种形式的输入，变量名的意思与题面描述相同：

• 1 u
• 2 u k c d
• 3 u c d
• 4 u v c d

输出格式

对于每个 $1$ 操作，输出一行一个非负整数表示答案。输出需要对 $998244353$ 取模。

样例 1 输入

7 12
1 2
2 3
1 4
4 5
1 6
6 7
0 0 0 0 0 0 0
2 1 2 10 1
3 1 10 2
4 2 5 10 3
3 2 10 4
2 3 2 10 5
1 1
1 2
1 3
1 4
1 5
1 6
1 7

样例 1 输出

1235
12345
1245
123
123
12
12

样例 2 $\sim$ 6

见选手目录下 $tree/ex\_tree2\sim 6.in$ 和 $tree/ex\_tree2\sim 6.out$。

数据分别满足子任务 $2\sim 6$ 的限制。

数据范围

保证所有数据满足：$2\le n,Q\le 10^5$，$0\le c,d<998244353$，$0\le k\le 10$。