Задане кореневе дерево. Вершина номер \(R\) є коренем дерева.

Кожна вершина в дереві має певну вагу.

Необхідно обробити \(Q\) запитів наступного виду:

\(1 V X\) - додати до ваги вершини \(V\) значення \(X\)
\(2 V\) - знайти суму ваг всіх вершин піддерева вершини \(V\)

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

В першому рядку три цілі числа \(N,Q,R\), довжина рядків (\(1 \le N,Q,Q \le 10^6\)).
В наступному рядку \(N\) цілих чисел \(Wi\) - вага кожної вершини (\(-10^6 \le Wi \le 10^6\)).
В наступних \(N-1\) рядках перераховані ребра дерева (номера двох вершин).
В кожному з наступних \(Q\) рядків міститься опис запиту (число \(X\) в запитах виду \(1 V X\) буде лежати в межах \(-10^6 \le X \le 10^6\))

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

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

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

10 14 9
12 -6 -4 -3 12 8 9 6 6 2
8 2
2 10
8 6
2 7
7 1
6 3
10 9
2 4
10 5
1 4 -1
2 2
1 7 -1
2 10
1 10 5
2 1
1 7 -5
2 5
1 1 8
2 7
1 8 8
2 2
1 5 5
2 6

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

21
34
12
12
23
31
4