Dane jest ukorzenione drzewo składające się z $N$ wierzchołków. Wierzchołki są ponumerowane od $1$ do $N$. Wierzchołek $i$ ma wagę $A_i$. Początkowo korzeniem jest wierzchołek $r$.

Napisz program wykonujący następujące zapytania:

• 0 x y: Zamień wagi wierzchołków w poddrzewie wierzchołka x na y.
• 1 r: Zmień korzeń drzewa na r.
• 2 x y z: Zamień wagi wierzchołków na ścieżce między x a y na z.
• 3 x: Wypisz minimalną wagę w poddrzewie wierzchołka x.
• 4 x: Wypisz maksymalną wagę w poddrzewie wierzchołka x.
• 5 x y: Dodaj y do wag wszystkich wierzchołków w poddrzewie wierzchołka x.
• 6 x y z: Dodaj z do wag wszystkich wierzchołków na ścieżce między x a y.
• 7 x y: Wypisz minimalną wagę na ścieżce między x a y.
• 8 x y: Wypisz maksymalną wagę na ścieżce między x a y.
• 9 x y: Zmień rodzica wierzchołka x na y. Jeśli wierzchołek y znajduje się w poddrzewie wierzchołka x, zignoruj to zapytanie.
• 10 x y: Wypisz sumę wag na ścieżce między x a y.
• 11 x: Wypisz sumę wag w poddrzewie wierzchołka x.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $N$, $M$ ($1 \le N, M \le 10^5$).

Następne $N-1$ wierszy zawiera po dwie liczby całkowite $u, v$ ($1 \le u, v \le N$) oznaczające krawędź łączącą te wierzchołki.

Następne $N$ wierszy zawiera wagę $A_i$ wierzchołka $i$.

Następny wiersz zawiera początkowy numer korzenia $r$ ($1 \le r \le N$).

Następne $M$ wierszy zawiera zapytania opisane powyżej.

Wszystkie liczby całkowite podane na wejściu mogą być reprezentowane w typie C++ int, a dane wejściowe są tak dobrane, że podczas przetwarzania zapytań suma wag wszystkich wierzchołków nie przekracza zakresu int.

Wyjście

Dla każdego zapytania wypisz wynik w osobnym wierszu, w kolejności występowania.

Przykład

Wejście 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

Wyjście 1

9
1
1

Wejście 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

Wyjście 2

173
860
103
791
608
1557