题目描述

这是一道模板题。

给定数列 \(a\)，你需要依次进行 \(q\) 个指令，指令有两类：

• \(1\) \(i\) \(x\)：将 \(a_i\) 加上 ；
• \(2\) \(l\) \(r\)：询问 \(\sum \limits_{i=l}^r a_i\) 的值。

输入输出格式

第一行输入两个正整数 \(n\) 和 \(q\)。

第二行 \(n\) 个整数，表示 \(a\) 数组。

第 \(3\) 至 \(q+2\) 行，每行三个整数，代表一个指令。

输出 \(0\) 至 \(q\) 行，每行为一个询问的答案。

输入输出样例

输入样例：

3 2
1 2 3
1 2 0
2 1 3

输出样例：

6

数据范围

\(1 \le n,q \le 10^6,-10^6\le a_i \le10^6,x\le10^6\)