题目描述

小陶最近在学数据结构，助教给他们布置了一道上机题，但是小陶不会做，你能帮帮他吗？

在一个有 $n$ 个数的数列上进行 $m$ 次操作，操作有两种：

$1\ x\ c$： 将数列中第 $x$ 个数加上 $c$

$2\ x\ y$：求出第 $x$ 个数、第 $x+1$ 个数、$...$、第 $y$ 个数的和

输入格式

第一行两个正整数 $n,m$ ；（ $n,m \le 2e5$ ）

第二行 $n$ 个整数，表示初始的数列；

之后 $m$ 行，每行三个整数描述一个操作。

输出格式

对于每个操作 $2$ ，输出一行一个数表示答案。

样例输入输出

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

14
16

2 2
0 0 
1 1 1
2 1 2

1

说明/提示

对于 $30 \%$ 的数据: $n, m \leq 5000$

对于 $60 \%$ 的数据: $n, m \leq 30000$

对于 $100 \%$ 的数据: $n, m<200000$，$c<1e9$