Реалізуйте Heavy-Light decomposition і за її допомогою відповідайте на запити знаходження суми на шляху між двома вершинами.

Формат вхідних даних

В першому рядку число \(N\) - кліькість вершин дерева (\(1 \le N \le 2*10^5\))
В наступному рядку \(N\) цілих чисел - значення у вершинах. (\(1 \le Ai \le 10^9\)) В кожному з наступних \(N-1\) рядків по два числа \(v1,v2\) які описують ребра дерева. (\(1 \le v1,v2 \le 2*10^5\))
В третьому рядку число \(M\) - кількість запитів (\(1 \le M \le 2*10^5\))
В кожному з наступних \(M\) рядків по три числа \(type,q1,q2\)
Якщо type=1 , то необхідно в вершині q1 додати число q2
Якщо type=2 , то необхідно визначити суму на шляху між вершинами q1 та q2

Корінь дерева - вершина з номером 1

Формат вихідних даних

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

Приклад вхідних даних

5 3
2 4 1 3 3
1 2
1 3
2 4
2 5
2 3 5
1 2 2
2 3 5

Приклад вихідних даних

10 12