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

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\).