题目描述

zcwwzdjn 在追杀 zhx ，而 zhx 逃入了一个遥远的国度。当 zcwwzdjn 准备进入遥远的国度继续追杀时，守护神 RapiD 阻拦了 zcwwzdjn 的去路，他需要 zcwwzdjn 完成任务后才能进入遥远的国度继续追杀。

问题是这样的：遥远的国度有 $n$ 个城市，这些城市之间由一些路连接且这些城市构成了一颗树。这个国度有一个首都，我们可以把这个首都看做整棵树的根，但遥远的国度比较奇怪，首都是随时有可能变为另外一个城市的。遥远的国度的每个城市有一个防御值，第 $i$ 个的防御值为 $val_i$，有些时候 RapiD 会使得某两个城市之间的路径上的所有城市的防御值都变为某个值。

RapiD 想知道在某个时候，如果把首都看做整棵树的根的话，那么以某个城市为根的子树的所有城市的防御值最小是多少。

由于 RapiD 无法解决这个问题，所以他拦住了 zcwwzdjn 希望他能帮忙。但 zcwwzdjn 还要追杀 zhx，所以这个重大的问题就被转交到了你的手上。

输入格式

第 $1$ 行两个整数 $n\ m$，代表城市个数和操作数。

第 $2$ 行至第 $n$ 行，每行两个整数 $u\ v$，代表城市 $u$ 和城市 $v$ 之间有一条路。

第 $n+1$ 行，有 $n$ 个整数，第 $i$ 个代表第 $i$ 个点的初始防御值 $val_i$。

第 $n+2$ 行一个整数 $id$，代表初始的首都为 $id$。

第 $n+3$ 行至第 $n+m+2$ 行，首先有一个整数 $opt$。

如果 $opt=1$，接下来有一个整数 $id$，代表把首都修改为 $id$；

如果 $opt=2$，接下来有三个整数 $x\ y\ v$，代表将 $x\ y$ 路径上的所有城市的防御值修改为 $v$；

如果 $opt=3$，接下来有一个整数 $id$，代表询问以城市 $id$ 为根的子树中的最小防御值。

输出格式

对于每个 $opt=3$ 的操作，输出一行代表对应子树的最小点权值。

3 7
1 2
1 3
1 2 3
1
3 1
2 1 1 6
3 1
2 2 2 5
3 1
2 3 3 4
3 1

1
2
3
4

提示

对于 $20\%$ 的数据，$n\le 1000,m\le 1000$。

对于另外 $10\%$ 的数据，$n\le 100000,m\le 100000$，保证修改为单点修改。

对于另外 $10\%$ 的数据，$n\le100000,m \le 100000$，保证树为一条链。

对于另外 $10\%$ 的数据，$n\le 100000,m\le100000$，没有修改首都的操作。

对于 $100\%$ 的数据，$1 \leq n\le 100000,1 \leq m \le 100000,0<val_i<2^{31}$。