Складніші запити на дереві

Limits: 2 sec., 256 MiB

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

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

• 1$\ u \ v \ x$ — збільшити значення $a$ всім вершинам на шляху від $u$ до $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 4 5 2 2 2 2 1 1 4 3 7 2 1	18 26 24 32 60

Notes

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

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

• Піддерево вершини $1$ — це ціле дерево. Відповідь дорівнює $a_1+a_2+a_3+a_4+a_5=4+7+4+7+4=26$.

• На шляху від вершини $4$ до вершини $5$ лежать вершини $4$, $2$, $5$. Після збільшення $a_4$, $a_2$, $a_5$ на $2$ масив $a$ стане $(4, 9, 4, 9, 6)$.

• Піддерево вершини $2$ складається з вершин $2$, $4$, $5$. Відповідь дорівнює $a_2+a_4+a_5=9+9+6=24$.

• Піддерево вершини $1$ — це ціле дерево. Відповідь дорівнює $a_1+a_2+a_3+a_4+a_5=4+9+4+9+6=32$.

• На шляху від вершини $4$ до вершини $3$ лежать вершини $4$, $2$, $1$, $3$. Після збільшення $a_4$, $a_2$, $a_1$, $a_3$ на $7$ масив $a$ стане $(11, 16, 11, 16, 6)$.

• Піддерево вершини $1$ — це ціле дерево. Відповідь дорівнює $a_1+a_2+a_3+a_4+a_5=11+16+11+16+6=60$.