小C同学认为跑步非常有趣，于是决定制作一款叫做《天天爱跑步》的游戏。《天天爱跑步》需要玩家完成打卡任务。

这个游戏的地图可以看做一棵包含$n$个结点和$n-1$条边的树，每条边连接两个结点，且任意两个结点存在一条路径互相到达。树上结点的编号为从$1$到$n$的连续正整数。新的一天开始时，某个玩家在第$0$秒从自己的起点出发，以每秒跑一条边的速度，不间断地沿着最短路径向着自己的终点跑去，跑到终点后该玩家就算完成了打卡任务。(由于地图是一棵树，所以每个人的路径是唯一的)

小C想知道游戏的活跃度，所以在每个结点上都放置了一个观察员。在结点j的观察员会选择在第$W_j$秒观察玩家，一个玩家能被这个观察员观察到当且仅当该玩家在第 秒也正好到达了结点$j$。小C想知道每个观察员会观察到多少人？

注意：我们认为一个玩家到达自己的终点后该玩家就会结束游戏，他不能等待一段时间后再被观察员观察到。即对于把结点$j$作为终点的玩家：若他在$W_j$秒之前到达终点，则在结点$j$的观察员不能观察到该玩家；若他正好在第$W_j$秒到达终点，则在结点$j$的观察员可以观察到这个玩家。

但是这个游戏是在是太难了，所以游戏还增加了充钱的功能。具体来说，某人氪金后，可以对地图上的边进行修改，删除边$(a,b)$，并添加边$(c,d)$，同时，为了维持服务器正常运行，保证地图仍然是一棵树。随着树形态的变化，小C为了更全面地了解活跃度，决定在某些时刻修改某个$W_j$。

输入格式

第一行包含两个正整数 $n,m$ ，其中$n$代表结点的数量，同时也是观察员的数量，$m$代表事件的数量。

接下来$n-1$行，每行两个数$a,b$，描述这棵树。

接下来一行$n$个数，表示$1 \sim n$每个观察员的初始W值。

接下来$m$行，每行描述一个事件，有三种形式:

$1$ $a$ $b:$表示新的一天开始了，有一个玩家在时刻0从a沿最短路径跑到b

$2$ $a$ $b$ $c$ $d$:表示某人充了钱，把边$(a,b)$替换为了边$(c,d)$。保证$(a,b)$边存在，并且替换结束后仍然是一棵树。

$3$ $a$ $b$:表示小C决定把$a$号观察员的$W$修改为$b$

输出格式

$1$行$n$个数，第$j$个整数表示结点j的观察员可以观察到多少人。

样例一

input

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

output

2 0 0 1 1 1

限制与约定

对于20%的数据，无操作$2,3$

对于另20%​的数据，无操作$2$

对于另20%的数据，无操作$3$

对于另20%的数据，所有玩家经过路径总长$\le 10^8$

对于100%的数据，$n,m \le 10^5$

时间限制： $5\texttt{s} \times 2$

空间限制：$512\texttt{MB}$