$N$ vértices forman un árbol con raíz. Los vértices están numerados del $1$ al $N$. El vértice $i$ tiene un peso $A_i$. Inicialmente, el vértice $r$ es la raíz.

Escribe un programa que realice las siguientes consultas:

• 0 x y: Cambia el peso de los vértices en el subárbol de $x$ a $y$.
• 1 r: Cambia la raíz del árbol a $r$.
• 2 x y z: Cambia el peso de los vértices en el camino entre $x$ e $y$ a $z$.
• 3 x: Imprime el peso mínimo de los vértices en el subárbol de $x$.
• 4 x: Imprime el peso máximo de los vértices en el subárbol de $x$.
• 5 x y: Suma $y$ al peso de los vértices en el subárbol de $x$.
• 6 x y z: Suma $z$ al peso de los vértices en el camino entre $x$ e $y$.
• 7 x y: Imprime el peso mínimo de los vértices en el camino entre $x$ e $y$.
• 8 x y: Imprime el peso máximo de los vértices en el camino entre $x$ e $y$.
• 9 x y: Cambia el padre de $x$ a $y$. Si el vértice $y$ existe dentro del subárbol de $x$, ignora esta consulta.
• 10 x y: Imprime la suma de los pesos de los vértices en el camino entre $x$ e $y$.
• 11 x: Imprime la suma de los pesos de los vértices en el subárbol de $x$.

Entrada

La primera línea contiene dos enteros $N$, $M$. ($1 \le N, M \le 10^5$)

A continuación, $N-1$ líneas contienen dos vértices $u, v$ que conecta cada arista. ($1 \le u, v \le N$)

Luego, $N$ líneas contienen el peso $A_i$ del vértice $i$.

Después, se da el número del vértice raíz inicial $r$. ($1 \le r \le N$)

Finalmente, $M$ líneas contienen las consultas descritas anteriormente.

Todos los enteros dados en la entrada se pueden representar con el tipo int de C++, y la entrada está garantizada de modo que durante el procesamiento de las consultas, la suma de los pesos de todos los vértices no exceda el rango de int.

Salida

Para cada consulta, imprime el resultado en una línea separada en orden.

Ejemplos

Entrada 1

5 5
2 1
3 1
4 1
5 2
4
1
4
1
2
1
10 2 3
3 1
7 3 4
6 3 3 2
9 5 1

Salida 1

9
1
1

Entrada 2

10 12
2 1
3 2
4 2
5 3
6 4
7 5
8 2
9 4
10 9
791
868
505
658
860
623
393
717
410
173
4
0 8 800
1 4
2 8 2 103
3 9
4 4
5 7 304
6 8 8 410
7 10 8
8 1 8
9 6 9
10 2 3
11 5

Salida 2

173
860
103
791
608
1557