Soit un arbre enraciné composé de $N$ sommets. Les sommets sont numérotés de $1$ à $N$. Le sommet $i$ a un poids $A_i$. Initialement, le sommet $r$ est la racine.

Écrivez un programme qui exécute les requêtes suivantes :

• 0 x y : modifier le poids des sommets du sous-arbre de $x$ en $y$.
• 1 r : changer la racine de l'arbre en $r$.
• 2 x y z : modifier le poids des sommets sur le chemin reliant $x$ et $y$ en $z$.
• 3 x : afficher la valeur minimale des poids des sommets du sous-arbre de $x$.
• 4 x : afficher la valeur maximale des poids des sommets du sous-arbre de $x$.
• 5 x y : ajouter $y$ aux poids des sommets du sous-arbre de $x$.
• 6 x y z : ajouter $z$ aux poids des sommets sur le chemin reliant $x$ et $y$.
• 7 x y : afficher la valeur minimale des poids des sommets sur le chemin reliant $x$ et $y$.
• 8 x y : afficher la valeur maximale des poids des sommets sur le chemin reliant $x$ et $y$.
• 9 x y : changer le parent de $x$ en $y$. Si le sommet $y$ se trouve dans le sous-arbre de $x$, ignorer cette requête.
• 10 x y : afficher la somme des poids des sommets sur le chemin reliant $x$ et $y$.
• 11 x : afficher la somme des poids des sommets du sous-arbre de $x$.

Entrée

La première ligne contient deux entiers $N$, $M$. ($1 \le N, M \le 10^5$)

Les $N-1$ lignes suivantes contiennent chacune deux entiers $u, v$ représentant une arête reliant les sommets $u$ et $v$. ($1 \le u, v \le N$)

Les $N$ lignes suivantes contiennent chacune le poids $A_i$ du sommet $i$.

La ligne suivante contient l'entier $r$, le numéro du sommet racine initial. ($1 \le r \le N$)

Les $M$ lignes suivantes contiennent chacune une requête parmi celles décrites ci-dessus.

Tous les entiers donnés en entrée peuvent être représentés par le type int du C++, et les entrées sont telles que pendant le traitement des requêtes, la somme totale des poids de tous les sommets ne dépasse jamais la plage de int.

Sortie

Pour chaque requête produisant un résultat, afficher ce résultat sur une ligne séparée, dans l'ordre.

Exemples

Entrée 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

Sortie 1

9
1
1

Entrée 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

Sortie 2

173
860
103
791
608
1557