Запросы на сумму в диапазоне (Range Sum Queries) 2

Вам дан массив из n элементов и q запросов. Существует два типа запросов:

1. Получить сумму элементов на указанном отрезке

2. Обновить элемент массива в заданной позиции

Ваша задача — эффективно обработать эти запросы.

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

Первая строка содержит два целых числа n и q (1 ≤ n, q ≤ 100 000), которые обозначают количество элементов в массиве и количество запросов соответственно.

Вторая строка содержит n целых чисел, разделенных пробелами, (), являющихся начальными элементами массива.

Каждая из следующих q строк описывает один запрос:

1. Для запросов на сумму по диапазону: строка начинается с числа 1, за которым следуют два целых числа и (). Эти числа задают границы [ $$l_i, r_i$$ ], по которым нужно вычислить сумму элементов.

2. Для запросов на обновление массива: строка начинается с числа 2, за которым идут два целых числа и (), указывающих индекс элемента, который нужно обновить, и его новое значение .

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

Для каждого запроса на сумму по диапазону выведите сумму элементов в заданных границах в отдельной строке.

Примеры