Description

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

Format

Input

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

Output

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

Sample 1

Input

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 

Output

11
30
35

Limitation

1s, 256MiB for each test case.