题目描述

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

问题是这样的：遥远的国度有 $n$ 个城市，这些城市之间由一些路连接且这些城市构成了一颗树。这个国度有一个首都，我们可以把这个首都看做整棵树的根，但遥远的国度比较奇怪，首都是随时有可能变为另外一个城市的。遥远的国度的每个城市有一个防御值，有些时候 RapiD 会使得某两个城市之间的路径上的所有城市的防御值都变为某个值。RapiD 想知道在某个时候，如果把首都看做整棵树的根的话，那么以某个城市为根的子树的所有城市的防御值最小是多少。由于 RapiD 无法解决这个问题，所以他拦住了 zcwwzdjn 希望他能帮忙。但 zcwwzdjn 还要追杀 sb 的 zhx ，所以这个重大的问题就被转交到了你的手上。

输入格式

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

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

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

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

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

• 如果 $opt=1$，接下来有一个整数 $id$，代表把首都修改为 $id$；
• 如果 $opt=2$，接下来有三个整数 $p_1,p_2,v$，代表将 $p_1,p_2$ 路径上的所有城市的防御值修改为 $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 43 1

1
2
3
4

数据规模与提示

对于 $20\%$ 的数据，$n\le 10^3$，$m\le 10^3$。

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

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

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

对于 $100\%$ 的数据，$n\le 10^5，m\le 10^5$，$0<$ 所有权值 $\le 2^{31}$。