Stone Age Problem

Description:

Input:

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.

Output:

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.

Sample Input:

5 5
1 2 3 4 5
1 1 5
2 10
1 5 11
1 4 1
2 1

Sample Output:

19
50
51
42
5

Note:

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$$$.