C. Дерево подвижных сумм
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Яхуб очень любит деревья. Недавно он обнаружил интересное дерево под названием «дерево подвижных сумм». Дерево состоит из n вершин, пронумерованных от 1 до n, каждая вершина i содержит начальное значение ai. Корень дерева — вершина 1.

Это дерево имеет особое свойство: когда значение val добавляется к значению вершины i, значение -val добавляется ко всем значениям детей вершины i. Обратите внимание, что когда вы добавляете значение -val ребенку вершины i, вы также добавляете -(-val) ко всем детям этого ребенка вершины i и так далее. Для того, чтобы лучше понять описанное свойство, обратите внимание на пояснение к первому тесту.

Дерево поддерживает два типа запросов:

  • «1 x val» — добавить значение val к значению вершины x;
  • «2 x» — вывести текущее значение вершины x.

Чтобы помочь Яхубу лучше понять дерево, надо ответить на m запросов описанных типов.

Входные данные

В первой строке содержатся два целых числа n и m (1 ≤ n, m ≤ 200000). Во второй строке содержится n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 1000). В каждой из следующих n–1 строк содержится по два целых числа, ui и vi (1 ≤ ui, vi ≤ n), означающих, что существует ребро между вершинами ui и vi.

Каждая из следующих m строк содержит запрос в описанном выше формате. Гарантируется, что для всех запросов выполняется: 1 ≤ x ≤ n, 1 ≤ val ≤ 1000.

Выходные данные

Для каждого запроса второго типа (вывод текущего значения вершины) надо вывести ответ на запрос на отдельной строке. Ответы на запросы выводите в порядке следования запросов во входных данных.

Примеры
Входные данные
5 5
1 2 1 1 2
1 2
1 3
2 4
2 5
1 2 3
1 1 2
2 1
2 2
2 4
Выходные данные
3
3
0
Примечание

Изначально значения в вершинах равны [1, 2, 1, 1, 2].

Затем значение 3 добавляется к вершине 2. Вершина 2 передает значение -3 своим сыновьям, и далее значение -3 добавляется к вершинам 4 и 5. Дальше значение никуда не передается. После этого запроса значения в вершинах равны [1, 5, 1,  - 2,  - 1].

Затем значение 2 добавляется к вершине 1. Вершина 1 передает значение -2 своим сыновьям: вершине 2 и вершине 3. Из вершины 2 значение 2 передается вершинам 4 и 5. Вершина 3 не имеет сыновей, следовательно из нее значение не передается. После этого запроса значения в вершинах становятся равны [3, 3,  - 1, 0, 1].

С основными определениями, связанными с корневыми деревьями, можно ознакомиться по ссылке: http://ru.wikipedia.org/wiki/Дерево_(теория_графов)