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.


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


-----Examples-----

Input
5 5
1 2 3 4 5
1 1 5
2 10
1 5 11
1 4 1
2 1
Output
19
50
51
42
5


-----Note-----

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

Initial array is $[1, 2, 3, 4, 5]$.

After performing the first query, array equals to $[5, 2, 3, 4, 5]$. The sum of all elements is $19$.

After performing the second query, array equals to $[10, 10, 10, 10, 10]$. The sum of all elements is $50$.

After performing the third query, array equals to $[10, 10, 10, 10, 11$]. The sum of all elements is $51$.

After performing the fourth query, array equals to $[10, 10, 10, 1, 11]$. The sum of all elements is $42$.

After performing the fifth query, array equals to $[1, 1, 1, 1, 1]$. The sum of all elements is $5$.

Difficulty: EASY
Tags: Data structures

Implementation
Skill types: Data structures

Starter code:

Solutions:
import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
c = [-1] * n
X = 0
S = sum(a)
lst = -2
out = []
for idx in range(q):
	req = list(map(int, input().split()))
	if req[0] == 1:
		i = req[1] - 1
		x = req[2]
		current = X if c[i] < lst else a[i]
		S += x - current
		a[i] = x
		c[i] = idx
	else:
		X = req[1]
		S = X * n
		lst = idx
	out.append(str(S) + '\n')
print(''.join(out))


import sys
input = sys.stdin.readline

def solve():
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	bag = {}
	for i in range(n):
		bag[i + 1] = arr[i]
	S = sum(arr)
	val = None
	for _ in range(q):
		Q = list(map(int, input().split()))
		if Q[0] == 1:
			(_, i, x) = Q
			if i not in bag:
				bag[i] = x
				S += x - val
			else:
				S += x - bag[i]
				bag[i] = x
		else:
			(_, x) = Q
			S = x * n
			bag = {}
			val = x
		print(S)
	return
solve()


import sys
input = sys.stdin.readline

def int_num():
	return int(input())

def int_list():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def solve():
	(n, t) = int_list()
	a = int_list()
	d = {idx: v for (idx, v) in enumerate(a)}
	last = 0
	tot = sum(a)
	while t:
		op = int_list()
		if op[0] == 1:
			(idx, x) = (op[1] - 1, op[2])
			if idx in d:
				tot = tot - d[idx] + x
			else:
				tot = tot - last + x
			d[idx] = x
		else:
			x = op[1]
			tot = x * len(a)
			last = x
			d.clear()
		print(tot)
		t -= 1

def main():
	solve()
main()


import sys
input = sys.stdin.readline

def solve():
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	v = [0] * n
	cnt = 0
	last = 0
	ans = sum(arr)
	for __ in range(q):
		t = list(map(int, input().split()))
		if len(t) == 3:
			(i, x) = (t[1], t[2])
			i -= 1
			if v[i] == cnt:
				ans += x - arr[i]
				arr[i] = x
			else:
				arr[i] = x
				v[i] = cnt
				ans += x - last
		else:
			cnt += 1
			last = t[1]
			ans = t[1] * n
		print(ans)
solve()


import sys

def solve():
	inp = sys.stdin.readline
	(n, q) = map(int, inp().split())
	a = list(map(int, inp().split()))
	b = [None] * n
	for i in range(n):
		b[i] = (a[i], 0)
	last = (-1, 0)
	s = sum(a)
	for idx in range(q):
		ii = iter(map(int, inp().split()))
		t = next(ii)
		if t == 1:
			(i, x) = ii
			if last[0] < b[i - 1][1]:
				s -= b[i - 1][0]
			else:
				s -= last[1]
			s += x
			b[i - 1] = (x, idx)
		else:
			x = next(ii)
			last = (idx, x)
			s = x * n
		print(s)

def main():
	solve()
main()


import sys
input = sys.stdin.readline
(N, Q) = list(map(int, input().split()))
K = dict(enumerate(map(int, input().split())))
S = sum(K.values())
default = 0
for _ in range(Q):
	X = list(map(int, input().split()))
	if X[0] == 1:
		S -= K.get(X[1] - 1, default)
		S += X[2]
		K[X[1] - 1] = X[2]
	elif X[0] == 2:
		S = N * X[1]
		K = {}
		default = X[1]
	print(S)


from typing import Any, TYPE_CHECKING

class DefaultDict(dict):
	if TYPE_CHECKING:
		default: int

	def __init__(self, *args, **kwargs) -> None:
		self.default = kwargs.pop('default')
		super().__init__(*args, **kwargs)

	def __getitem__(self, key: int) -> Any:
		try:
			return super().__getitem__(key)
		except KeyError:
			return self.default
(n, q) = map(int, input().split())
array = DefaultDict(enumerate(map(int, input().split())), default=None)
total = sum(array.values())
results = []
for _ in range(q):
	query = input().split()
	if query[0] == '1':
		(_, i, x) = map(int, query)
		total += x - array[i - 1]
		array[i - 1] = x
		results.append(total)
	elif query[0] == '2':
		x = int(query[1])
		array.clear()
		array.default = x
		total = x * n
		results.append(total)
print('\n'.join((str(r) for r in results)))


f = open(0)
R = lambda : map(int, next(f).split())
(n, q) = R()
d = {}
i = v = r = 0
for x in R():
	r += x
	i += 1
	d[i] = x
while q:
	q -= 1
	(t, *x) = R()
	if t & 1:
		(i, x) = x
		r += x - d.get(i, v)
		d[i] = x
	else:
		d = {}
		(v,) = x
		r = v * n
	print(r)


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
l = list(map(int, input().split()))
s = sum(l)
d = {i + 1: l[i] for i in range(n)}
val = 0
for _ in range(q):
	b = list(map(int, input().split()))
	if b[0] == 1:
		s += b[2] - d.get(b[1], val)
		d[b[1]] = b[2]
	else:
		s = b[1] * n
		d = dict()
		val = b[1]
	print(s)


f = open(0)
R = lambda : map(int, f.readline().split())
(n, q) = R()
a = (*R(),)
r = sum(a)
d = dict()
for (i, e) in enumerate(a):
	d[i + 1] = e
v = -1
for _ in [0] * q:
	(t, *x) = R()
	if t == 1:
		(i, x) = x
		r += x - d.get(i, v)
		d[i] = x
	if t == 2:
		d = {}
		(v,) = x
		r = v * n
	print(r)


fptr = open(0)
(n, q) = map(int, next(fptr).split())
a = list(map(int, next(fptr).split()))
s = sum(a)
first = [-1] * n
x = 0
l = -10
for _ in range(q):
	temp = list(map(int, next(fptr).split()))
	i = temp[0]
	j = temp[1]
	if i == 1:
		val = temp[2]
		ind = j - 1
		cur = x if first[ind] < l else a[ind]
		s += val - cur
		a[ind] = val
		first[ind] = _
	else:
		s = j * n
		l = _
		x = j
	print(s)


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
d = {}
for i in range(n):
	d[i + 1] = a[i]
s = sum(a)
same = 'x'
for i in range(q):
	command = list(map(int, input().split()))
	if command[0] == 1:
		s = s - d.get(command[1], same) + command[2]
		d[command[1]] = command[2]
	else:
		s = n * command[1]
		same = command[1]
		d = {}
	print(s)


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
summ = sum(a)
pre = -1
for _ in range(q):
	s = list(map(int, input().split()))
	t = s[0]
	i = -1
	x = s[-1]
	if t == 1:
		i = s[1]
		if pre == -1:
			summ -= a[i - 1]
			a[i - 1] = x
			summ += a[i - 1]
		else:
			if i - 1 in d:
				summ -= d[i - 1]
			else:
				summ -= pre
			summ += x
			d[i - 1] = x
	else:
		pre = x
		d = dict()
		summ = x * n
	print(int(summ))


f = open(0)
(n, q) = map(int, next(f).split())
a = list(map(int, next(f).split()))
c = [-1] * n
X = 0
S = sum(a)
lst = -2
for idx in range(q):
	req = list(map(int, next(f).split()))
	if req[0] == 1:
		i = req[1] - 1
		x = req[2]
		current = X if c[i] < lst else a[i]
		S += x - current
		a[i] = x
		c[i] = idx
	else:
		X = req[1]
		S = X * n
		lst = idx
	print(S)


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a)
marker = {}
for i in range(n):
	marker[i + 1] = a[i]
x = 0
for _ in range(q):
	k = list(map(int, input().split()))
	if k[0] == 1:
		s += k[2] - marker.get(k[1], x)
		marker[k[1]] = k[2]
	else:
		marker.clear()
		s = k[1] * n
		x = k[1]
	print(s)


f = open(0)

def R():
	return map(int, f.readline().split())
(n, q) = R()
a = R()
total = 0
values = {0: -1}
for (i, x) in enumerate(a):
	values[i + 1] = x
	total += x
for _ in range(q):
	(t, *x) = R()
	if t == 1:
		(i, x) = x
		total += x - values.get(i, values[0])
		values[i] = x
	else:
		x = x[0]
		values = {0: x}
		total = n * x
	print(total)


import math as mt
from collections import defaultdict, deque
import sys
from bisect import bisect_right as b_r
from bisect import bisect_left as b_l
from os import path
from heapq import *
input = sys.stdin.readline
mod = 1000000007
INT_MAX = sys.maxsize - 1
INT_MIN = -sys.maxsize

def myyy__answer():
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	sm = sum(a)
	track = defaultdict(int)
	for i in range(n):
		track[i + 1] = 0
	st = 0
	cnt2 = 0
	for i in range(q):
		b = list(map(int, input().split()))
		if b[0] == 1:
			if track[b[1]] == cnt2:
				sm = sm - a[b[1] - 1] + b[2]
				a[b[1] - 1] = b[2]
			else:
				a[b[1] - 1] = b[2]
				track[b[1]] = cnt2
				sm = sm - st + b[2]
		else:
			sm = n * b[1]
			st = b[1]
			cnt2 += 1
		print(sm)
myyy__answer()


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
p_ql = 0
dic = {}
for i in range(n):
	dic[i + 1] = arr[i]
tot = sum(arr)
for i in range(q):
	ql = list(map(int, input().split()))
	if ql[0] == 2:
		dic.clear()
		tot = ql[1] * n
		print(tot)
		p_ql = ql[1]
	else:
		if ql[1] in dic:
			tot += ql[2] - dic[ql[1]]
			dic[ql[1]] = ql[2]
		else:
			tot += ql[2] - p_ql
			dic[ql[1]] = ql[2]
		print(tot)


import sys
inp = sys.stdin.readline
(n, q) = map(int, inp().split())
l = list(map(int, inp().split()))
d = {i: l[i] for i in range(n)}
x = 0
s = sum(l)
for _ in range(q):
	qu = list(map(int, inp().split()))
	if qu[0] == 2:
		d = {}
		x = qu[1]
		s = x * n
	else:
		(i, v) = (qu[1], qu[2])
		if i - 1 in d:
			s += v - d[i - 1]
			d[i - 1] = v
		else:
			s += v - x
			d[i - 1] = v
	print(s)


f = open(0)
R = lambda : map(int, f.readline().split())
(n, q) = R()
a = (*R(),)
r = sum(a)
d = {}
i = 0
for x in a:
	i += 1
	d[i] = x
v = 0
while q:
	q -= 1
	(t, *x) = R()
	if t < 2:
		(i, x) = x
		r += x - d.get(i, v)
		d[i] = x
	else:
		d = {}
		(v,) = x
		r = v * n
	print(r)


import sys
input = sys.stdin.readline
from collections import defaultdict
(n, q) = map(int, input().split())
arr = dict(enumerate(map(int, input().split())))
S = sum(arr.values())
for i in range(q):
	op = list(map(int, input().split()))
	if op[0] == 1:
		S += op[2] - arr[op[1] - 1]
		arr[op[1] - 1] = op[2]
	else:
		d = op[1]
		S = n * d
		arr = defaultdict(lambda : d)
	print(S)


from sys import *
input = stdin.readline
(a, b) = map(int, input().split())
c = list(map(int, input().split()))
p = -1
j = sum(c)
l = {}
for z in range(a):
	l[z] = c[z]
for y in range(b):
	d = list(map(int, input().split()))
	if d[0] == 1:
		if l.get(d[1] - 1) != None:
			s = l[d[1] - 1]
			l[d[1] - 1] = d[2]
			j -= s
			j += l[d[1] - 1]
			print(j)
		else:
			j -= p
			j += d[2]
			l[d[1] - 1] = d[2]
			print(j)
	else:
		p = d[1]
		l = {}
		j = d[1] * a
		print(j)


f = open(0)
R = lambda : map(int, next(f).split())

def ii():
	return int(input())
(n, q) = R()
i = v = r = 0
dic = {}
for x in R():
	i += 1
	dic[i] = x
	r += x
for _ in range(q):
	(t, *x) = R()
	if t & 1:
		(i, x) = x
		r -= dic.get(i, v) - x
		dic[i] = x
	else:
		(x,) = x
		dic = {}
		v = x
		r = v * n
	print(r)


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
var = sum(a)
v = [0] * n
con = 0
last = 0
for i in range(q):
	l = list(map(int, input().split()))
	if l[0] == 1:
		if v[l[1] - 1] == con:
			var = var + l[2] - a[l[1] - 1]
			a[l[1] - 1] = l[2]
		else:
			a[l[1] - 1] = l[2]
			v[l[1] - 1] = con
			var = var + l[2] - last
	else:
		con += 1
		last = l[1]
		var = l[1] * n
	print(var)


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
A = list(map(int, input().split()))
mapping = {}
total = 0
for (i, val) in enumerate(A):
	mapping[i + 1] = val
	total += val
default_value = None
for _ in range(q):
	query = list(map(int, input().split()))
	if query[0] == 1:
		total -= mapping.get(query[1], default_value)
		total += query[2]
		mapping[query[1]] = query[2]
	else:
		mapping = {}
		default_value = query[1]
		total = default_value * n
	print(total)


import math, sys
input = sys.stdin.readline
inf = 1e+18
mod = 10 ** 9 + 7
pi = math.pi
e = math.e
modinv = lambda x, m: pow(x, m - 2, m)
import bisect
import heapq
mod9 = 998244353
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a)
d = {i: a[i] for i in range(n)}
v = -1
for i in range(q):
	Q = list(map(int, input().split()))
	if Q[0] == 2:
		s = n * Q[1]
		d = {}
		v = Q[1]
	else:
		Q[1] -= 1
		if d.get(Q[1]) == None:
			s += Q[2] - v
		else:
			s += Q[2] - d[Q[1]]
		d[Q[1]] = Q[2]
	print(s)


import sys
input = sys.stdin.readline

def solve():
	(n, q) = map(int, input().split())
	uv = 0
	ut = -1
	time = 0
	inp = list(map(int, input().split()))
	total = sum(inp)
	arr = [[v, 0] for v in inp]
	while q:
		time += 1
		type = list(map(int, input().split()))
		if len(type) == 3:
			idx = type[1]
			val = type[2]
			idx -= 1
			if arr[idx][1] > ut:
				total += val - arr[idx][0]
			else:
				total += val - uv
			arr[idx][0] = val
			arr[idx][1] = time
		else:
			val = type[1]
			total = n * val
			uv = val
			ut = time
		print(total)
		q -= 1

def main():
	t = 1
	while t:
		solve()
		t -= 1
main()


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
d = list(map(int, input().split()))
(c, x, y) = (sum(d), 0, 0)
s = set()
for _ in range(q):
	(t, *w) = map(int, input().split())
	if t == 2:
		c = w[0] * n
		x = w[0]
		s = set()
		if y == 0:
			y = 1
		print(c)
	else:
		if w[0] - 1 not in s and y == 1:
			c -= x - w[1]
		else:
			c -= d[w[0] - 1] - w[1]
		d[w[0] - 1] = w[1]
		s.add(w[0] - 1)
		print(c)


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
d = {}
s = sum(arr)
x = 0
for i in range(n):
	d[i + 1] = arr[i]
for i in range(q):
	l1 = list(map(int, input().split()))
	if l1[0] == 1:
		s += l1[2] - d.get(l1[1], x)
		d[l1[1]] = l1[2]
	else:
		s = l1[1] * n
		d.clear()
		x = l1[1]
	print(s)


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
ans = sum(a)
d = dict()
for i in range(n):
	d[i + 1] = a[i]
for _ in range(q):
	query = list(map(int, input().split()))
	if query[0] == 1:
		(t, i, x) = query
		if i not in d:
			ans -= tmp
		else:
			ans -= d[i]
		ans += x
		d[i] = x
	else:
		(t, x) = query
		tmp = x
		ans = tmp * n
		d.clear()
	print(ans)


from collections import defaultdict
import sys
input = sys.stdin.readline
(N, Q) = map(int, input().split())
A = dict(enumerate(map(int, input().split())))
S = sum(A.values())
for _ in range(Q):
	query = list(map(int, input().split()))
	if query[0] == 1:
		S += query[2] - A[query[1] - 1]
		A[query[1] - 1] = query[2]
	else:
		i = query[1]
		A = defaultdict(lambda : i)
		S = query[1] * N
	print(S)


import sys
input = sys.stdin.readline
(n, q) = list(map(int, input().split()))
arr = list(map(int, input().split()))
current_sum = sum(arr)
changed = False
ht = {}
value = 0
for i in range(q):
	new = list(map(int, input().split()))
	if new[0] == 1 and (not changed):
		current_sum -= arr[new[1] - 1]
		arr[new[1] - 1] = new[2]
		current_sum += new[2]
	elif new[0] == 2:
		ht = {}
		current_sum = new[1] * n
		changed = True
		value = new[1]
	elif new[1] - 1 in ht:
		current_sum -= ht[new[1] - 1]
		current_sum += new[2]
	else:
		ht[new[1] - 1] = new[2]
		current_sum -= value
		current_sum += new[2]
	print(current_sum)


import sys
(n, q) = map(int, sys.stdin.readline().split())
lst = list(map(int, sys.stdin.readline().split()))
s = sum(lst)
se = set()
f = -1
for j in range(q):
	lst1 = list(map(int, sys.stdin.readline().split()))
	if lst1[0] == 2:
		x = lst1[1]
		f = x
		print(x * n)
		s = x * n
		se.clear()
	else:
		ind = lst1[1] - 1
		x = lst1[2]
		if f == -1:
			s = s - lst[ind] + x
			print(s)
			lst[ind] = x
		elif ind not in se:
			s = s - f + x
			print(s)
			se.add(ind)
			lst[ind] = x
		else:
			s = s - lst[ind] + x
			print(s)
			lst[ind] = x


import sys
input = sys.stdin.readline
for _ in range(1):
	x = input().split()
	(n, q) = (int(x[0]), int(x[1]))
	a = input().split()
	for i in range(n):
		a[i] = int(a[i])
	s = sum(a)
	cur = -1
	fl = -1
	f = [0 for i in range(n)]
	for i in range(q):
		r = input().split()
		m = int(r[0])
		if m == 1:
			x = int(r[1]) - 1
			y = int(r[2])
			if f[x] >= fl:
				s += y - a[x]
				a[x] = y
			else:
				s += y - cur
				a[x] = y
			f[x] = i + 1
		elif m == 2:
			x = int(r[1])
			cur = x
			fl = i + 1
			s = x * n
		print(s)


import sys
input = sys.stdin.readline
(num, q) = map(int, input().split())
n = list(map(int, input().split()))
var = set(range(num))
x = -1
s = sum(n)
while q > 0:
	boo = list(map(int, input().split()))
	if boo[0] == 1:
		if boo[1] - 1 in var:
			s -= n[boo[1] - 1]
			n[boo[1] - 1] = boo[2]
			s += boo[2]
		else:
			s -= x
			n[boo[1] - 1] = boo[2]
			s += boo[2]
			var.add(boo[1] - 1)
	else:
		var.clear()
		s = num * boo[1]
		x = boo[1]
	q -= 1
	print(s)


import sys
input = sys.stdin.readline
(n, q) = [int(i) for i in input().split()]
a = list(map(int, input().split()))
a_sum = sum(a)
for i in range(q):
	content = [int(i) for i in input().split()]
	t = content[0]
	if t == 1 and type(a) == list:
		a_sum = a_sum - a[content[1] - 1] + content[2]
		a[content[1] - 1] = content[2]
		print(a_sum)
	elif t == 1 and type(a) == dict:
		temp = a.get(content[1] - 1, False)
		if temp is False:
			a_sum = a_sum - common + content[2]
		else:
			a_sum = a_sum - a[content[1] - 1] + content[2]
		a[content[1] - 1] = content[2]
		print(a_sum)
	else:
		common = content[1]
		a = dict()
		a_sum = n * content[1]
		print(a_sum)


import sys
input = lambda : sys.stdin.readline().strip()
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a)
y = 0
old = 0
d = dict()
for i in range(q):
	li = list(map(int, input().split()))
	if li[0] == 1:
		if y == 0:
			s -= a[li[1] - 1]
			s += li[2]
			a[li[1] - 1] = li[2]
			print(s)
		else:
			if li[1] in d:
				s += li[2] - d[li[1]]
				d[li[1]] = li[2]
			else:
				s += li[2]
				s -= old
				d[li[1]] = li[2]
			print(s)
	else:
		y = 1
		d = {}
		s = n * li[1]
		old = li[1]
		print(s)


from collections import defaultdict

def invr():
	return list(map(int, input().split()))

def invrdict():
	return dict(enumerate(map(int, input().split())))
import sys
input = sys.stdin.readline
(n, q) = invr()
A = invrdict()
s = sum(A.values())
for _ in range(q):
	qry = invr()
	if qry[0] == 1:
		s += qry[2] - A[qry[1] - 1]
		A[qry[1] - 1] = qry[2]
	else:
		i = qry[1]
		A = defaultdict(lambda : i)
		s = qry[1] * n
	print(s)


import sys

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))
(n, q) = [int(x) for x in input().split()]
sum = 0
listy = get_ints()
list2 = [0] * n
sec = 0
laqu = -1
for j in range(n):
	sum += listy[j]
for i in range(q):
	query = get_ints()
	if len(query) == 3:
		ind = query[1] - 1
		val = query[2]
		if list2[ind] > laqu:
			sum += val - listy[ind]
			list2[ind] = i
			listy[ind] = val
		else:
			sum += val - sec
			listy[ind] = val
			list2[ind] = i
	else:
		sum = n * query[1]
		sec = query[1]
		laqu = i
	print(sum)


(n, q) = map(int, input().split())
l = list(map(int, input().split()))
s = sum(l)
u = False
d = {}

def solve(n, l, q, s, u, d):
	ans = []
	for i in range(q):
		l1 = list(map(int, input().split()))
		if l1[0] == 1:
			if not u:
				t = l[l1[1] - 1]
				l[l1[1] - 1] = l1[2]
				s = s + l1[2] - t
				print(s)
			elif d.get(l1[1] - 1):
				t = l[l1[1] - 1]
				l[l1[1] - 1] = l1[2]
				s = s + l1[2] - t
				ans.append(s)
				d[l1[1] - 1] = 1
			else:
				l[l1[1] - 1] = l1[2]
				s = s + l1[2] - up
				ans.append(s)
				d[l1[1] - 1] = 1
		else:
			u = True
			up = l1[1]
			s = n * l1[1]
			ans.append(s)
			d = {}
	return ans
ans = solve(n, l, q, s, u, d)
for val in ans:
	print(val)


from collections import defaultdict
import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
D = dict(enumerate(map(int, input().split())))
current_sum = sum(D.values())
for _ in range(q):
	new_request = list(map(int, input().split()))
	if new_request[0] == 1:
		(i, x) = (new_request[1], new_request[2])
		current_sum += x - D[i - 1]
		D[i - 1] = x
	else:
		number = new_request[1]
		D = defaultdict(lambda : number)
		current_sum = number * n
	print(current_sum)


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
s = sum(a)
last = -1
a = [[i, last] for i in a]
for i in range(q):
	v = input().split()
	if v[0] == '1':
		(_, ind, x) = map(int, v)
		ind -= 1
		if a[ind][1] < last:
			s += x - z
			a[ind] = [x, last]
		else:
			s += x - a[ind][0]
			a[ind][0] = x
	else:
		(_, x) = map(int, v)
		last = i
		z = x
		s = z * n
	print(s)


inp = [list(map(int, l.split())) for l in open(0).read().splitlines()]
(n, q) = inp[0]
a = inp[1]
last = 0
step = [-1] * n
laststep = -2
tot = sum(a)
for (i, b) in enumerate(inp[2:]):
	if b[0] == 1:
		if step[b[1] - 1] > laststep:
			tot += b[2] - a[b[1] - 1]
			a[b[1] - 1] = b[2]
		else:
			tot += b[2] - last
			a[b[1] - 1] = b[2]
		step[b[1] - 1] = i
		print(tot)
	else:
		tot = b[1] * n
		last = b[1]
		laststep = i
		print(tot)


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
sm = sum(arr)
each = -1
ss = set()
for i in range(n):
	ss.add(i)
for _ in range(q):
	ll = list(map(int, input().split()))
	if ll[0] == 1:
		ll[1] -= 1
		if ll[1] in ss:
			prev = arr[ll[1]]
		else:
			prev = each
		ss.add(ll[1])
		arr[ll[1]] = ll[2]
		sm += ll[2] - prev
	else:
		ss = set()
		each = ll[1]
		sm = each * n
	print(sm)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
(n, q) = inlt()
arr = inlt()
current_sum = sum(arr)
current_version = 0
last_update = None
arr = [(value, current_version) for value in arr]
arr_len = len(arr)
for _ in range(q):
	args = inlt()
	if args[0] == 1:
		i = args[1] - 1
		x = args[2]
		(el_value, el_version) = arr[i]
		if el_version < current_version:
			current_sum += x - last_update
		else:
			current_sum += x - el_value
		arr[i] = (x, current_version)
	else:
		x = args[1]
		current_version += 1
		last_update = x
		current_sum = arr_len * x
	print(current_sum)


import sys
input = sys.stdin.readline
(n, qq) = map(int, input().split())
w = [0] + list(map(int, input().split()))
s = sum(w)
v = [-1] * (qq + 1)
last1 = [-1] * (n + 1)
last2 = int(-1)

def now(i):
	if last1[i] == last2 == -1:
		return w[i]
	if last1[i] == -1:
		return v[last2]
	if last2 == -1:
		return v[last1[i]]
	return v[max(last2, last1[i])]
for i in range(qq):
	q = list(map(int, input().split()))
	if q[0] == 1:
		(a, b) = (q[1], q[2])
		v[i] = b
		s -= now(a)
		last1[a] = i
		s += now(a)
	else:
		a = q[1]
		s = n * a
		last2 = i
		v[i] = a
	print(s)


import sys
input = sys.stdin.readline
(n, q) = map(int, input().split())
a = list(map(int, input().split()))
sum1 = sum(a)
D = dict()
elems = []
f = True
for i in range(q):
	be = []
	s = list(map(int, input().split()))
	if s[0] == 1:
		be.append(int(s[1]) - 1)
		be.append(int(s[2]))
		if f != False:
			el = be[0]
			el2 = a[el]
			sum1 -= el2
			sum1 += be[1]
			print(sum1)
			a[be[0]] = be[1]
		elif be[0] in elems:
			sum1 -= D[be[0]]
			sum1 += be[1]
			D[be[0]] = be[1]
			print(sum1)
		else:
			sum1 -= D[len(a)]
			sum1 += be[1]
			D[be[0]] = be[1]
			print(sum1)
			elems.append(be[0])
	else:
		D = dict()
		D[len(a)] = int(s[1])
		sum1 = n * int(s[1])
		print(sum1)
		f = False
		elems = []


inp = list(map(int, input().split()))
ne = inp[0]
nq = inp[1]
a = list(map(int, input().split()))
ans = sum(a)
equalArray = False
equalVal = 0
opt = []
d = {}
for ii in range(ne):
	d[ii] = a[ii]
for _ in range(nq):
	q = list(map(int, input().split()))
	if q[0] == 1:
		prevVal = d.get(q[1] - 1, equalVal)
		ans += q[2] - prevVal
		d[q[1] - 1] = q[2]
		equalArray = False
	else:
		d = {}
		ans = q[1] * ne
		equalArray = True
		equalVal = q[1]
	opt.append(ans)
print(*opt, sep='\n')


def solve(n, q, a, queries):
	two_happened = False
	exceptions = set()
	two_value = 0
	total_sum = sum(a)
	for query in queries:
		if query[0] == 1:
			(position, new_value) = (query[1] - 1, query[2])
			if not two_happened:
				total_sum += new_value - a[position]
				a[position] = new_value
				print(total_sum)
			elif position in exceptions:
				total_sum += new_value - a[position]
				a[position] = new_value
				print(total_sum)
			else:
				total_sum += new_value - two_value
				exceptions.add(position)
				a[position] = new_value
				print(total_sum)
		else:
			new_value = query[1]
			if not two_happened:
				two_happened = True
			exceptions = set()
			two_value = new_value
			total_sum = n * two_value
			print(total_sum)
(n, q) = [int(component) for component in input().split(' ')]
a = [int(component) for component in input().split(' ')]
queries = []
for _ in range(q):
	queries.append([int(component) for component in input().split(' ')])
solve(n, q, a, queries)


(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
qrr = [list(map(int, input().split())) for _ in range(q)]
(lastIndexOne, lastIndexTwo, lastTwoVal, lastArrOne, res) = (-1, -1, 0, [-1] * n, sum(arr))
for i in range(q):
	query = qrr[i]
	if query[0] == 2:
		res = query[1] * n
		print(res)
		lastIndexTwo = i
		lastTwoVal = query[1]
	else:
		res += query[2] - (lastTwoVal if lastIndexTwo >= 0 and lastIndexTwo > lastArrOne[query[1] - 1] else arr[query[1] - 1])
		lastArrOne[query[1] - 1] = i
		arr[query[1] - 1] = query[2]
		print(res)


from collections import Counter
from functools import lru_cache
from bisect import bisect, bisect_left
result = []
(n, q) = map(int, input().split())
array = list(map(int, input().split()))
queries = []
for i in range(q):
	queries.append(list(map(int, input().split())))
currentSum = sum(array)
visited = set()
changed = 0
for query in queries:
	if len(query) == 2:
		(_, num) = query
		changed = num
		currentSum = num * n
		visited = set()
	else:
		(_, idx, num) = query
		idx -= 1
		if changed and idx not in visited:
			visited.add(idx)
			currentSum -= changed
		else:
			currentSum -= array[idx]
		currentSum += num
		array[idx] = num
	print(currentSum)


import sys
sys.setrecursionlimit(10 ** 5)

def pro(arr, qu):
	n = len(arr)
	tot = sum(arr)
	each = 0
	flg = None
	store = set()
	f = 0
	for q in qu:
		if q[0] == 2:
			print(q[1] * n)
			each = q[1]
			tot = q[1] * n
			flg = 1
			store = set()
		else:
			(type, p, v) = q
			i = p - 1
			if flg or (flg != None and i not in store):
				tot = tot + v - each
				arr[i] = v
				flg = 0
				store.add(i)
			else:
				tot = tot + v - arr[i]
				arr[i] = v
				store.add(i)
			print(tot)
(n, q) = list(map(int, input().split()))
arr = list(map(int, input().split()))
qu = []
for i in range(q):
	qu.append(list(map(int, input().split())))
pro(arr, qu)


(n, q) = map(int, input().split(' '))
arr = list(map(int, input().split(' ')))
allsame = 0
queries = []
dictans = {i + 1: arr[i] for i in range(n)}
ans = sum(arr)
dicts = []
dicts.append(dictans)
for i in range(q):
	query = list(map(int, input().split(' ')))
	if query[0] == 2:
		dicts.append({'all': query[1]})
	queries.append(query)
dictpointer = 0
for i in range(q):
	query = queries[i]
	if query[0] == 2:
		dictpointer += 1
		ans = n * query[1]
		print(ans)
		continue
	else:
		if query[1] in dicts[dictpointer]:
			ans += query[2] - dicts[dictpointer][query[1]]
		else:
			ans += query[2] - dicts[dictpointer]['all']
		dicts[dictpointer][query[1]] = query[2]
		print(ans)
		continue


import math as m
[n, q] = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
qs = []
for a in range(0, q):
	qs += [[int(x) for x in input().split()]]
s = sum(arr)
all_same = False
val = -1
changed_indices = []
changed_vals = []
for q in qs:
	if q[0] == 1:
		i = q[1] - 1
		v = q[2]
		if not all_same:
			s += v - arr[i]
			arr[i] = v
		else:
			try:
				pos = changed_indices.index(i)
				s += v - changed_vals[pos]
				changed_vals[pos] = v
			except:
				s += v - val
				changed_indices += [i]
				changed_vals += [v]
	else:
		all_same = True
		val = q[1]
		s = n * val
		changed_indices = []
		changed_vals = []
	print(s)


(n, q) = map(int, input().split())
l = list(map(int, input().split()))
queries = []
for i in range(q):
	temp = list(map(int, input().split()))
	queries.append(temp)
s = sum(l)
onall = -1
d = {}
for i in range(n):
	d[i] = [l[i]]
for u in queries:
	if u[0] == 1:
		if u[1] - 1 in d:
			diff = u[2] - d[u[1] - 1][-1]
			s += diff
			d[u[1] - 1].append(u[2])
		else:
			diff = u[2] - onall
			s += diff
			d[u[1] - 1] = [u[2]]
	else:
		s = n * u[1]
		onall = u[1]
		d = {}
	print(s)


def main():
	out = ''
	(n, q) = [int(x) for x in input().split()]
	input_ = [int(x) for x in input().split()]
	modified = {i: input_[i] for i in range(len(input_))}
	value = 0
	sum_ = sum(input_)
	for k in range(q):
		input_ = [int(x) for x in input().split()]
		if input_[0] == 1:
			i = input_[1] - 1
			sum_ += input_[2]
			if i in modified:
				sum_ -= modified[i]
			else:
				sum_ -= value
			modified[i] = input_[2]
		else:
			value = input_[1]
			modified = {}
			sum_ = value * n
		out += str(sum_) + '\n'
	print(out)
main()


(n, q) = map(int, input().split())
data = {index: int(value) for (index, value) in enumerate(input().split(), start=1)}
summ = sum(data.values())
default = None
for qi in range(q):
	params = input().split()
	if params[0] == '1':
		key = int(params[1])
		value = int(params[2])
		summ += value - data.get(key, default)
		data[key] = value
	else:
		default = int(params[1])
		summ = default * n
		data = {}
	print(summ)


def inpList():
	return [int(i) for i in input().split()]

def solve():
	(n, q) = inpList()
	a = inpList()
	t1 = {}
	t2 = 0
	sm = sum(a)
	for qi in range(q):
		inp = inpList()
		if len(inp) == 3:
			(_, i, x) = inp
			if t1.get(i):
				sm += x - t1[i]
			else:
				sm += x - (t2 or a[i - 1])
			t1[i] = x
		else:
			(_, x) = inp
			t2 = x
			sm = t2 * n
			t1 = {}
		print(sm)
solve()


def solve():
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	c = [-1] * n
	X = 0
	S = sum(a)
	lst = -2
	for idx in range(q):
		req = list(map(int, input().split()))
		if req[0] == 1:
			i = req[1] - 1
			x = req[2]
			current = X if c[i] < lst else a[i]
			S += x - current
			a[i] = x
			c[i] = idx
		else:
			X = req[1]
			S = X * n
			lst = idx
		print(S)
solve()


def solve():
	(n, q) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	ind = [i for i in range(1, n + 1)]
	DI = dict(zip(ind, arr))
	now = 0
	SU = sum(arr)
	for i in range(q):
		b = list(map(int, input().split()))
		if b[0] == 2:
			DI = {}
			now = b[1]
			SU = n * now
			print(SU)
		else:
			SU += b[2] - DI.get(b[1], now)
			DI[b[1]] = b[2]
			print(SU)
solve()


import collections
import math
import sys
from queue import PriorityQueue
from random import randint
RANDOM = randint(1, 10 ** 9)

def main(testnumber):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	s = sum(a)
	last = -1
	query_value = {}
	for i in range(n):
		query_value[i] = a[i]
	for i in range(q):
		qr = list(map(int, input().split()))
		if qr[0] == 1:
			qn = qr[1] - 1
			if qn not in query_value:
				vv = last
			else:
				vv = query_value[qn]
			query_value[qn] = qr[2]
			s -= vv
			s += qr[2]
		else:
			query_value.clear()
			last = qr[1]
			s = last * n
		print(s)
t = 1
cnt = 1
while t > 0:
	main(cnt)
	cnt += 1
	t -= 1


(n, q) = map(int, input().split())
a = list(map(int, input().split()))
current_sum = sum(a)
changed = set([i + 1 for i in range(n)])
init = 0
for _ in range(q):
	query = input().split()
	if query[0] == '1':
		(i, x) = (int(query[1]), int(query[2]))
		if i in changed:
			current_sum -= a[i - 1]
			current_sum += x
		else:
			current_sum = current_sum - init + x
			changed.add(i)
		a[i - 1] = x
	else:
		x = int(query[1])
		current_sum = x * n
		init = x
		changed = set()
	print(current_sum)


(n, k) = [int(x) for x in input().split(' ')]
a = [int(x) for x in input().split(' ')]
ans = sum(a)
last_i = -1
pre = [0] * 200010
val = -1
for i in range(1, k + 1):
	tokens = input().split(' ')
	if len(tokens) == 3:
		idx = int(tokens[1]) - 1
		cval = int(tokens[2])
		if pre[idx] < last_i:
			pre[idx] = last_i
			a[idx] = val
		ans += cval - a[idx]
		a[idx] = cval
		print(ans)
	else:
		last_i = i
		val = int(tokens[1])
		ans = val * n
		print(ans)


def solve():
	(n, q) = map(int, input().split())
	aa = [0] + [int(a) for a in input().split()]
	res = sum(aa)
	base = 0
	notbase = set(range(n + 1))
	for _ in range(q):
		(t, *d) = map(int, input().split())
		if t == 1:
			(i, x) = d
			if i in notbase:
				res += x - aa[i]
			else:
				res += x - base
				notbase.add(i)
			aa[i] = x
		else:
			notbase = set()
			base = d[0]
			res = base * n
		print(res)

def main():
	solve()
main()