Yuno is playing a galgame called Irotoridori no Sekai.
It's a good game, so she decided to make a data structure problem for you.
You are given a tree with $n$ nodes, each node has a value.
You need to perform three operations:
$1~x~y$ : reverse all the value of nodes on the chain $x$ -> $y$
$2~x~y~z$ : add $z$ to the value of nodes on the chain $x$ -> $y$
$3~x~y$ Then followed by $y$ numbers $v_1,v_2, ... v_y$ : output the $v_1$th, $v_2$th, ... , $v_y$th smallest value of the nodes which distance on the tree is no more than $1$ from node $x$
First line contains two numbers $n,m$.
Second line $n$ numbers indicating the value of the first node to the last node.
The next $n - 1$ lines, every line consists of two numbers $x,y$, indicating that there exists an edge between node $x$ and node $y$.
In the next $m$ lines, every line consists of an operation described above.
For each query, output a number indicating the answer.
5 5
1 2 3 4 5
1 2
2 3
3 4
4 5
3 1 2 1 2
3 2 3 1 2 3
3 3 4 1 2 3 4
3 4 2 1 2
3 5 2 1 2
1
2
1
2
3
2
3
4
5
3
4
3
5