数据结构

题目描述

给定一个序列 $a$，你需要维护对于该序列的 $q$ 次操作：

1 x y，令 $a_x \leftarrow y$。

2 y，将数组中所有数改成 $y$。

每次操作完成后，输出当前数组中所有元素的总和。

输入格式

第一行两个整数 $n,q$。

第二行 $n$ 个整数，表示 $a$ 中的元素。

接下来有 $q$ 行，首先输入一个整数 $t$。

若 $t=1$，接着输入两个整数 $x,y$。

若 $t=2$，接着输入一个整数 $y$。

输出格式

共 $q$ 行，每行一个整数，表示当前数组 $a$ 中所有元素的和。

样例 #1

样例输入 #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

提示

对于 $50\%$ 的数据，满足 $1\le n,q\le 5000$。

对于 $100\%$ 的数据，满足 $1\le n,q\le 2\times 10^5$，$1\le a_i,y\le 10^9$。