题目描述

给定数列$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，表示数列长度和询问个数。保证$1 \le n,q \le10^6$。 第二行n个整数$a[1],a[2], \dots,a[n]$，表示初始数列。保证$|a[i]| \le10^6$。

接下来q行，每行一个操作，为以下两种之一：

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

2 l r：给定l,r，求$\sum_{i=l}^ra[i]$的值。保证$1 \le l \le r \le n,$ $|x| \le10^6$。

输出描述

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

示例1

输入

3 2
1 2 3
1 2 0
2 1 3

输出

6

备注

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