描述

给出一个序列,有n个数,编号为1~n
该序列支持单点修改,区间求和

输入

第一行,两个整数n,m,表示序列长度和操作次数
第二行,n个整数,表示初始序列
第3~m+2行,每行第一个整数表示操作类型,1表示修改,2表示询问
若为修改,则后面输入两个整数,第一个整数表示要修改的位置(编号),第二个整数为修改后的值
若为询问,则后面输入两个整数l,r,表示询问当前序列的子区间\([l,r]\)中所有数据的和

输出

对于每个询问输出一行,只有一个整数,表示询问的区间和

输入样例

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

输出样例

10
13
14

数据范围和限制'

对于前40%的数据,n<=2000,m<=5000
对于100%的数据,\(n\leq100000,m\leq200000,1\leq l\leq r\leq n,序列中的数\leq10^9\)
时间限制1s,空间限制256m