CF1679B.Stone Age Problem

Once upon a time Mike and Mike decided to come up with an outstanding problem for some stage of ROI (rare olympiad in informatics). One of them came up with a problem prototype but another stole the idea and proposed that problem for another stage of the same olympiad. Since then the first Mike has been waiting for an opportunity to propose the original idea for some other contest... Mike waited until this moment!

You are given an array $a$ of $n$ integers. You are also given $q$ queries of two types:

• Replace $i$-th element in the array with integer $x$.
• Replace each element in the array with integer $x$.

After performing each query you have to calculate the sum of all elements in the array.

从前，两位 Mike 决定为某届 ROI（罕见信息学奥林匹克竞赛）设计一道出色的题目。其中一位提出了一个题目的雏形，但另一位却窃取了这个创意，并将该题目提交给了同一届奥林匹克竞赛的另一场赛事。自那以后，第一位 Mike 便一直在等待机会，将原始创意提交给其他比赛……Mike 一直等到了此刻！

给你一个包含 $n$ 个整数的数组 $a$，以及 $q$ 个查询，查询分为两种类型：

• 将数组中第 $i$ 个元素替换为整数 $x$；
• 将数组中所有元素均替换为整数 $x$。

在每次执行查询后，你都需要计算并输出数组中所有元素的和。

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$) — the number of elements in the array and the number of queries, respectively.

The second line contains $n$ integers $a_1, \ldots, a_n$ ($1 \le a_i \le 10^9$) — elements of the array $a$.

Each of the following $q$ lines contains a description of the corresponding query. Description begins with integer $t$ ($t \in {1, 2}$) which denotes a type of the query:

• If $t = 1$, then two integers $i$ and $x$ are following ($1 \le i \le n$, $1 \le x \le 10^9$) — position of replaced element and it's new value.
• If $t = 2$, then integer $x$ is following ($1 \le x \le 10^9$) — new value of each element in the array.

第一行包含两个整数 $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$）—— 表示数组中每个元素的新值。

Print $q$ integers, each on a separate line. In the $i$-th line print the sum of all elements in the array after performing the first $i$ queries.

输出 $q$ 个整数，每个整数占一行。在第 $i$ 行中，输出执行前 $i$ 个查询后数组中所有元素的和。

Consider array from the example and the result of performing each query:

1. Initial array is $[1, 2, 3, 4, 5]$.
2. After performing the first query, array equals to $[5, 2, 3, 4, 5]$. The sum of all elements is $19$.
3. After performing the second query, array equals to $[10, 10, 10, 10, 10]$. The sum of all elements is $50$.
4. After performing the third query, array equals to $[10, 10, 10, 10, 11$]. The sum of all elements is $51$.
5. After performing the fourth query, array equals to $[10, 10, 10, 1, 11]$. The sum of all elements is $42$.
6. After performing the fifth query, array equals to $[1, 1, 1, 1, 1]$. The sum of all elements is $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$。