题目描述

这是一道模板题。 给定数列$a[1],a[2], \dots,a[n]$，你需要依次进行q个操作，操作有两类：

• 1 i x：给定i,x，将a[i]加上x；
• 2 l r：给定l,r，求$\sum_{i=l}^ra[i]$的值（换言之，求$a[l]+a[l+1]+ \dots+a[r]$的值）。

输入描述

第一行包含2个正整数n,q，表示数列长度和询问个数。 第二行n个整数$a[1],a[2], \dots,a[n]$，表示初始数列。 接下来q行，每行一个操作，为以下两种之一：

1 i x：给定i,x，将a[i]加上x；

2 l r：给定l,r，求$\sum_{i=l}^ra[i]$的值。

输出描述

对于每个2lr操作输出一行，每行有一个整数，表示所求的结果。

示例1

输入

3 2
1 2 3
1 2 0
2 1 3

输出

6

备注

输入样例 #2

10 20
8235 10404 450 26811 16136 13289 24985 6269 17704 22414 
1 5 2
1 1 6
2 6 7
1 8 9
2 8 9
1 4 8
1 3 5
1 6 5
2 4 9
2 1 4
1 9 5
2 6 7
1 6 4
1 2 9
2 2 8
2 6 7
2 4 5
1 2 9
2 1 4
2 3 5

输出样例 #2

38274
23982
105218
45919
38279
98386
38283
42957
45937
43412

输入样例 #3

10 20
8251 31378 24235 16055 2173 155 7779 24401 1958 24441 
2 8 9
2 4 5
2 2 6
2 10 10
1 2 4
1 7 5
1 6 3
2 3 4
1 6 2
2 4 9
1 1 7
2 5 5
1 9 10
1 5 6
1 6 10
2 4 9
2 1 9
2 4 5
1 7 9
1 8 4

输出样例 #3

26359
18228
73996
24441
40290
52531
2173
52557
116432
18234

数据范围

对于所有数据，$1 \le n,q \le 10^6,$ $|a[i]| \le 10^6$,$1 \le l \le r \le n,$ $|x| \le10^6$。

保证$1 \le n,q \le10^6$。

保证$|a[i]| \le10^6$。

保证$1 \le l \le r \le n,$ $|x| \le10^6$。