P3979 A Distant Kingdom

`zcwwzdjn` is hunting down `zhx`, and `zhx` has fled to a distant kingdom. When `zcwwzdjn` is about to enter the distant kingdom to continue the pursuit, the guardian `RapiD` blocks his way. He must complete a task before he can enter the distant kingdom and continue the chase. Here is the problem: the distant kingdom has $n$ cities. These cities are connected by some roads and they form a tree. The kingdom has a capital, and we can regard this capital as the root of the whole tree; however, the capital may change to another city at any time. Each city has a defense value; the $i$-th city's defense value is $val_i$. Sometimes `RapiD` will set the defense values of all cities on the path between two cities to a certain value. `RapiD` wants to know, at some moment, if we regard the capital as the root of the whole tree, then what is the minimum defense value among all cities in the subtree rooted at some city. Since `RapiD` cannot solve this, he stopped `zcwwzdjn` hoping he could help. But `zcwwzdjn` still needs to hunt down `zhx`, so this important problem has been handed over to you.

Line $1$: two integers $n\ m$, representing the number of cities and the number of operations. Lines $2$ to $n$: each line contains two integers $u\ v$, meaning there is a road between city $u$ and city $v$. Line $n+1$: $n$ integers; the $i$-th integer is the initial defense value $val_i$ of the $i$-th city. Line $n+2$: one integer $id$, meaning the initial capital is $id$. Lines $n+3$ to $n+m+2$: first there is an integer $opt$. - If $opt=1$, then there is an integer $id$, meaning the capital is updated to $id$. - If $opt=2$, then there are three integers $x\ y\ v$, meaning the defense values of all cities on the path $x\ y$ are set to $v$. - If $opt=3$, then there is an integer $id$, meaning you need to query the minimum defense value in the subtree rooted at city $id$ (with the current capital regarded as the root of the whole tree).

For each $opt=3$ operation, output one line containing the minimum defense value in the corresponding subtree.

For $20\%$ of the testdata, $n\le 1000,m\le 1000$. For another $10\%$ of the testdata, $n\le 100000,m\le 100000$, and updates are guaranteed to be point updates. For another $10\%$ of the testdata, $n\le100000,m \le 100000$, and the tree is guaranteed to be a chain. For another $10\%$ of the testdata, $n\le 100000,m\le100000$, and there are no operations that change the capital. For $100\%$ of the testdata, $1 \leq n\le 100000,1 \leq m \le 100000,0