题目描述

有一棵包含 $n$ 个节点的灵能网络，网络结构是一棵树，根节点为 $1$。每条边的长度均为 $1$。

每个节点 $u$ 上都有一个能量值 $x_u$。树上两点之间的距离定义为它们之间唯一简单路径上的边数。

接下来有 $Q$ 次事件，每次事件属于下面四种之一。

事件 1：查询单点

给定一个节点 $u$，询问当前节点 $u$ 的能量值。查询不会改变任何节点的能量值。

事件 2：局部波动

给定一个节点 $u$ 和三个非负整数 $k,c,d$。

对于所有与 $u$ 的距离不超过 $k$ 的节点 $v$，将其能量值更新为

事件 3：子树共振

给定一个节点 $u$ 和两个非负整数 $c,d$。

对于所有位于 $u$ 子树中的节点 $v$，将其能量值更新为

事件 4：路径传导

给定两个节点 $u,v$ 和两个非负整数 $c,d$。

对于 $u$ 到 $v$ 的简单路径上的所有节点 $w$，包括端点 $u,v$，将其能量值更新为

对于每次事件 1，输出查询结果。所有输出结果均对 $998244353$ 取模。

输入格式

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

接下来 $n-1$ 行，每行两个正整数 $u,v$，表示树上的一条边。

接下来一行 $n$ 个非负整数，依次表示初始能量值 $x_1,x_2,\dots,x_n$。

接下来 $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\le n,Q\le 10^5$，$0\le c,d<998244353$，$0\le k\le 10$。