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

Яхуб очень любит деревья. Недавно он обнаружил интересное дерево под названием «дерево подвижных сумм». Дерево состоит из 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/Дерево_(теория_графов)