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

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