$N$ вершин корневого дерева. Вершины пронумерованы от 1 до $N$. Вершина $i$ имеет вес $A_i$. Изначально корнем является вершина $r$.

Напишите программу, выполняющую следующие запросы:

• 0 x y: заменить вес всех вершин в поддереве $x$ на $y$.
• 1 r: изменить корень дерева на $r$.
• 2 x y z: заменить вес всех вершин на пути между $x$ и $y$ на $z$.
• 3 x: вывести минимальный вес среди вершин в поддереве $x$.
• 4 x: вывести максимальный вес среди вершин в поддереве $x$.
• 5 x y: прибавить $y$ к весу всех вершин в поддереве $x$.
• 6 x y z: прибавить $z$ к весу всех вершин на пути между $x$ и $y$.
• 7 x y: вывести минимальный вес среди вершин на пути между $x$ и $y$.
• 8 x y: вывести максимальный вес среди вершин на пути между $x$ и $y$.
• 9 x y: заменить родителя вершины $x$ на $y$. Если вершина $y$ находится в поддереве $x$, то проигнорировать этот запрос.
• 10 x y: вывести сумму весов вершин на пути между $x$ и $y$.
• 11 x: вывести сумму весов вершин в поддереве $x$.

Входные данные

В первой строке даны два целых числа $N$, $M$ ($1 \le N, M \le 10^5$).

Далее следуют $N-1$ строк, каждая содержит два целых числа $u, v$ — номера вершин, соединённых ребром ($1 \le u, v \le N$).

Далее следуют $N$ строк, $i$-я строка содержит вес $A_i$ вершины $i$.

Далее дано целое число $r$ — номер изначального корня ($1 \le r \le N$).

Далее следуют $M$ строк, каждая содержит один запрос, описанный выше.

Все целые числа, данные на входе, представимы типом int в C++. Гарантируется, что в процессе выполнения запросов сумма весов всех вершин не выходит за пределы диапазона int.

Выходные данные

Для каждого запроса, требующего вывода, выведите результат на отдельной строке в порядке появления запросов.

Примеры

Пример ввода 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

Пример вывода 1

9
1
1

Пример ввода 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

Пример вывода 2

173
860
103
791
608
1557