Description

给定n个数列，规定有两种操作，一是修改某个元素，二是求子数列[a,b]的连续和。数列的元素个数最多100000个，询问操作最多100000次。

Input Format

第一行2个整数n,m（n表示输入n个数列，m表示有m个操作） 第二行输入n个数列。 接下来M行，每行有三个数k,a,b(k=0表示求子数列[a,b]的和，k=1表示第a个数列加b)

Output Format

输出若干行数字，表示每次K=0时对应输出一个子数列[a,b]的连续和。

Sample

输入样列

10  5
1 2 3 4 5 6 7 8 9 10 
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8

输出样例

11
30
35

Hint

0<n<=100000,0<m<=100000.