Найпростіші запити на дереві

Limits: 2 sec., 256 MiB

Задано кореневе дерево з $n$ вершин, пронумерованих від $1$ до $n$. Коренем дерева є вершина $1$. У кожній вершині $v$ записано ціле число $a_v$.

Потрібно опрацювати $q$ запитів двох типів.

• 1$\ v \ x$ — збільшити значення $a$ всім вершинам у піддереві вершини $v$ на $x$.

• 2$\ v$ — знайти максимальне значення $a$ в піддереві вершини $v$.

Input

У першому рядку задано ціле число $n$ — кількість вершин дерева.

У другому рядку задано $n$ цілих чисел $a_v$, що записані у вершинах.

У наступних $n - 1$ рядках записано по два цілих числа $u$, $v$ — номери вершин, з’єднані ребром.

Далі задано ціле число $q$ — кількість запитів.

У наступних $q$ рядках задано запити у вищеописаному форматі.

Output

Для кожного запиту другого типу виведіть відповідь в окремому рядку.

Constraints

$1 \le n \le 2 \cdot 10^5$,

$1 \le q \le 2 \cdot 10^5$,

$1 \le a_v, x \le 10^9$.

Samples

Input (stdin) сopy	Output (stdout) сopy
5 4 7 4 7 4 1 2 1 3 2 4 2 5 7 2 2 2 1 1 2 37 2 2 2 1 1 3 43 2 1	7 7 44 44 47

Notes

Спочатку $a = (4, 7, 4, 7, 4)$.

• Піддерево вершини $2$ складається з вершин $2$, $4$, $5$. Відповідь дорівнює $\max \{a_2, a_4, a_5\} = \max \{7, 7, 4\} = 7$.

• Піддерево вершини $1$ — це ціле дерево. Відповідь дорівнює $\max a = 7$.

• Піддерево вершини $2$ складається з вершин $2$, $4$, $5$. Після збільшення $a_2$, $a_4$ та $a_5$ на $37$ масив $a$ стане $(4, 44, 4, 44, 41)$.

• Піддерево вершини $2$ складається з вершин $2$, $4$, $5$. Відповідь дорівнює $\max \{a_2, a_4, a_5\} = \max \{44, 44, 41\} = 44$.

• Піддерево вершини $1$ — це ціле дерево. Відповідь дорівнює $\max a = 44$.

• Піддерево вершини $3$ містить одну вершину $3$. Після збільшення $a_3$ на $43$ масив $a$ стане $(4, 44, 47, 44, 41)$.

• Піддерево вершини $1$ — це ціле дерево. Відповідь дорівнює $\max a = 47$.