Когда-то давно Миша и Миша решили придумать интересную задачу на очередной этап РОИ (редкая олимпиада по информатике). Один из них придумал прототип задачи, но другой своровал идею и предложил задачу на другой этап этой же олимпиады. С тех пор первый Миша ждал возможности предложить оригинальную идею на какую-либо другую олимпиаду... Ждал Миша до этого момента!
Вам дан массив \(a\) из \(n\) целых чисел. Также даны \(q\) запросов двух типов:
После выполнения каждого запроса вы должны вычислить сумму всех элементов в массиве.
Первая строка содержит два целых числа \(n\) и \(q\) (\(1 \le n, q \le 2 \cdot 10^5\)) — количество элементов в массиве и количество запросов, соответственно.
Вторая строка содержит \(n\) целых чисел \(a_1, \ldots, a_n\) (\(1 \le a_i \le 10^9\)) — элементы массива \(a\).
Каждая из следующих \(q\) строк содержит описание очередного запроса. Описание запроса начинается с целого числа \(t\) (\(t \in \{1, 2\}\)), которое обозначает тип запроса:
Выведите \(q\) целых чисел, каждое в отдельной строке. В \(i\)-й строке нужно вывести сумму всех элементов массива после выполнения первых \(i\) запросов.
Рассмотрим массив из примера и результат выполнения каждого запроса:
5 5 1 2 3 4 5 1 1 5 2 10 1 5 11 1 4 1 2 1
19 50 51 42 5
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач