HOME_W的附加题

给定n个数a1,a2,a3,……an。和m次操作。

每次操作格式如下

x y k   表示将a[x]替换为y。并求替换后，前k小的数之和

单组数据，每组数据开头是两个整数n,m。

接下一行有n个整数 a1,a2,a3,……n

再接下来一行，每行有三个整数x，y，k。

100<=n,m<=100,000

1<=ai,x,y,k<=n

对于每个操作输出一行，只包含一整数，代表前k小之和

10 10
6 3 7 3 1 6 6 10 3 3
9 10 3
3 10 5
6 5 7
10 6 5
3 10 9
6 4 1
4 1 6
3 1 3
10 4 1
3 10 1

7
16
27
18
50
1
21
3
1
1