Description

这是一道模板题。

给定数列，你需要依次进行\( a[1], a[2], \dots, a[n] \)个操作，操作有两类：

• 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] \)的值）。

Format

Input

第一行包含\( 2 \)个正整数，表示数列长度和询问个数。保证\( 1\le n,q\le 10^6 \)。
第二行\( n \)个整数\( a[1], a[2], \dots, a[n] \) ，表示初始数列。保证\( |a[i]|\le 10^6 \)。
接下来\( 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] \)的值）。

保证\( 1\le l\le r\le n, \) \( |x|\le 10^6 \) 。

Output

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

Sample 1

Input

3 2
1 2 3
1 2 0
2 1 3

Output

6

Limitation

3s, 256 MiB for each test case.

Hint

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

Source

LibreOJ 130
树状数组 1：单点修改，区间查询