【题目描述】

有一个遥远的国度，其中有 $n$ 个城市，城市之间由 $n-1$ 条道路连接，并且这些道路构成一棵树。

这个国度有一个首都。我们可以把首都看作整棵树的根，但首都会随着操作发生改变。

每个城市都有一个防御值，第 $i$ 个城市的初始防御值为 $val_i$。系统需要支持如下操作：

• 修改首都；
• 将某两个城市之间简单路径上的所有城市防御值全部改成同一个给定值；
• 在当前首都作为根时，询问以某个城市为根的子树中所有城市防御值的最小值。

请你依次处理所有操作。

【输入格式】

第一行输入两个整数 $n,m$，表示城市数量和操作数量。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示城市 $u$ 和城市 $v$ 之间有一条道路。

接下来一行输入 $n$ 个整数，第 $i$ 个整数表示城市 $i$ 的初始防御值 $val_i$。

接下来一行输入一个整数 $id$，表示初始首都为城市 $id$。

接下来 $m$ 行，每行先输入一个整数 $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

【提示】

对于部分数据，$n,m \le 1000$；对于部分数据，保证修改为单点修改；对于部分数据，保证树是一条链；对于部分数据，没有修改首都的操作。

对于全部数据，$1 \le n,m \le 100000$，点权和修改值在 32 位有符号整数范围内。