Яхуб очень любит деревья. Недавно он обнаружил интересное дерево под названием «дерево подвижных сумм». Дерево состоит из n вершин, пронумерованных от 1 до n, каждая вершина i содержит начальное значение ai. Корень дерева — вершина 1.
Это дерево имеет особое свойство: когда значение val добавляется к значению вершины i, значение -val добавляется ко всем значениям детей вершины i. Обратите внимание, что когда вы добавляете значение -val ребенку вершины i, вы также добавляете -(-val) ко всем детям этого ребенка вершины i и так далее. Для того, чтобы лучше понять описанное свойство, обратите внимание на пояснение к первому тесту.
Дерево поддерживает два типа запросов:
- «1 x val» — добавить значение val к значению вершины x;
- «2 x» — вывести текущее значение вершины x.
Чтобы помочь Яхубу лучше понять дерево, надо ответить на m запросов описанных типов.
Выходные данные
Для каждого запроса второго типа (вывод текущего значения вершины) надо вывести ответ на запрос на отдельной строке. Ответы на запросы выводите в порядке следования запросов во входных данных.
Примечание
Изначально значения в вершинах равны [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/Дерево_(теория_графов)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|