You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

现有一个长度为 $n$ 序列 $a$，然后给出$k$个操作 $(u,v)$ ：使 $a_u=v$ 。

每次操作后，快速求出修改之后的序列和。

输入描述

输入第一行两个正整数$n,k$。（$3 \leq n \leq 10^6，1 \leq k \leq 10^6$）

接下来一行 $n$ 个正整数，第i个数代表 $a_i$ 。（$1 \leq a_i \leq 10^9$）

接下来 $k$ 行，每行两个整数 $(u,v)$ ，表示将索引为 $u$ 的元素修改为 $v$ 。

输出描述

输出共 $k$ 行，每行输出一个整数，表示序列和。

样例1

样例输入

3 1
1 1 4
1 5

样例输出

10

样例2

样例输入

5 4
1 2 3 4 5
1 2
3 2
4 2
5 2

样例输出

16
15
13
10