Codeforces и Polygon могут быть недоступны в период с 23 мая, 7:00 (МСК) по 23 мая, 11:00 (МСК) в связи с проведением технических работ. ×

B. Задача каменного века
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Когда-то давно Миша и Миша решили придумать интересную задачу на очередной этап РОИ (редкая олимпиада по информатике). Один из них придумал прототип задачи, но другой своровал идею и предложил задачу на другой этап этой же олимпиады. С тех пор первый Миша ждал возможности предложить оригинальную идею на какую-либо другую олимпиаду... Ждал Миша до этого момента!

Вам дан массив $$$a$$$ из $$$n$$$ целых чисел. Также даны $$$q$$$ запросов двух типов:

  • Заменить $$$i$$$-й элемент массива на число $$$x$$$.
  • Заменить каждый элемент массива на число $$$x$$$.

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

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

Первая строка содержит два целых числа $$$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\}$$$), которое обозначает тип запроса:

  • Если $$$t = 1$$$, далее следуют два целых числа $$$i$$$ и $$$x$$$ ($$$1 \le i \le n$$$, $$$1 \le x \le 10^9$$$) — позиция элемента, который нужно изменить, и его новое значение.
  • Если $$$t = 2$$$, далее следует целое число $$$x$$$ ($$$1 \le x \le 10^9$$$) — число, на которое нужно заменить каждый элемент массива.
Выходные данные

Выведите $$$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
Примечание

Рассмотрим массив из примера и результат выполнения каждого запроса:

  1. Изначально массив равен $$$[1, 2, 3, 4, 5]$$$.
  2. После выполнения первого запроса массив равен $$$[5, 2, 3, 4, 5]$$$. Сумма всех элементов равна $$$19$$$.
  3. После выполнения второго запроса массив равен $$$[10, 10, 10, 10, 10]$$$. Сумма всех элементов равна $$$50$$$.
  4. После выполнения третьего запроса массив равен $$$[10, 10, 10, 10, 11$$$]. Сумма всех элементов равна $$$51$$$.
  5. После выполнения четвертого запроса массив равен $$$[10, 10, 10, 1, 11]$$$. Сумма всех элементов равна $$$42$$$.
  6. После выполнения пятого запроса массив равен $$$[1, 1, 1, 1, 1]$$$. Сумма всех элементов равна $$$5$$$.