题目描述

给定数列$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]$的值。

输出描述

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

示例1

输入

3 2
1 2 3
1 2 0
2 1 3

输出

6

备注

输入样例 #2

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

输出样例 #2

7

输入样例 #3

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

输出样例 #3

10
6
0
6
16
6
24
14
50
41

数据范围

对于所有数据，$1 \le n,q \le10^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$。