遥远的国度

题目描述

`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$ 的操作,输出一行代表对应子树的最小点权值。

输入输出样例

输入样例 #1

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

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\le2^{31}$。