很久以前,Mike 和 Mike 决定为 ROI 的某个阶段提出一个突出问题(罕见的信息学奥林匹克竞赛)。其中一个人提出了一个问题原型,但另一个人窃取了这个想法,并在同一届奥林匹克竞赛的另一个阶段提出了这个问题。从那时起,第一个迈克就一直在等待机会,为其他比赛提出最初的想法……迈克等到了这一刻!
给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。您还会收到两种类型的 $$$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$$$ 行中打印数组中所有元素的总和。
示例
输入 #1
5 5 1 2 3 4 5 1 1 5 2 10 1 5 11 1 4 1 2 1
输出 #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$$$。