Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В Темерии поднялось восстание скоя'таэлей. Они разбились на мелкие отряды и нападают на небольшие заставы, деревни и караваны. Геральту нужно перевезти Цири через охваченную восстанием страну, поэтому желательно держаться наиболее безопасных мест. Помогите Геральту определять, какие из деревень на пути защищены лучше других.
В Темерии `N` деревень, связанных `M` двусторонними дорогами. Во всех деревнях стоят небольшие гарнизоны, численность которых постоянно меняется: кто-то отбывает, чтобы сопровождать караван, а кто-то получает подкрепление. Защищённостью деревни назовём суммарное число защитников в ней и во всех деревнях, непосредственно связанных с ней дорогами (более далёкие гарнизоны всё равно не успеют прибыть на помощь в случае нападения).
Вам даётся `Q` запросов одного из двух типов:
* число защитников в `i`-й деревне изменяется на `d`;
* нужно определить защищённость деревни под номером `i`.
Выведите ответы на все запросы второго типа.
В первой строке входных данных содержатся `3` неотрицательных целых числа `N`, `M` и `Q` — число деревень, дорог и запросов соответственно (`1 <= N, Q <= 10^5`, `0 <= M <= 10^5`).
Во второй строке содержится `N` неотрицательных целых чисел `a_i` — численности гарнизонов в деревнях до выполнения запросов (`0 <= a_i <= 10^5`).
Затем следует `M` строк, содержащих по `2` различных целых числа `u`, `v` в каждой (`1 <= u, v <= N`) — описания дорог. Дорога связывает между собой деревни с номерами `u` и `v`, между любой парой деревень существует не более одной дороги, и никакая дорога не связывает деревню саму с собой.
Затем следует `Q` строк, описывающих запросы. Гарантируется, что среди запросов есть хотя бы один запрос второго типа.
Для запроса первого типа строка содержит `3` целых числа: тип запроса `1`, номер деревни `i` (`1 <= i <= N`) и изменение числа защитников `d` (`-10^5 <= d <= 10^5`). Гарантируется, что число защитников никогда не становится отрицательным.
Для запроса второго типа строка содержит `2` целых числа: тип запроса `1` и номер деревни `i` (`1 <= i <= N`).
Выведите по одному числу для каждого запроса типа `2`: общее количество защитников в деревне с номером `i` и её непосредственных соседях.
```sample Пример ввода
6 5 7
0 5 2 3 2 0
1 2
3 4
3 5
4 5
4 6
2 4
1 6 10
2 6
1 3 -1
1 5 -1
2 4
2 1
```
```sample Пример вывода
7
13
15
5
```
Начало
Рабочее место участника
Дерево отрезков, декартово дерево, √-декомпозиция