Problem: Write a program which manipulates a sequence A = {a1, a2, . . . , an} with the following operations:

* add(i, x): add x to ai.
* getSum(s, t): print the sum of as, as+1,...,at.



Note that the initial values of ai (i = 1, 2, . . . , n) are 0.

Constraints

* 1 ≤ n ≤ 100000
* 1 ≤ q ≤ 100000
* If comi is 0, then 1 ≤ xi ≤ n, 0 ≤ yi ≤ 1000.
* If comi is 1, then 1 ≤ xi ≤ n, 1 ≤ yi ≤ n.

Input


n q
com1 x1 y1
com2 x2 y2
...
comq xq yq


In the first line, n (the number of elements in A) and q (the number of queries) are given. Then, q queries are given where com represents the type of queries. '0' denotes add(xi, yi) and '1' denotes getSum(xi, yi).

Output

For each getSum operation, print the sum in a line.

Example

Input

3 5
0 1 1
0 2 2
0 3 3
1 1 2
1 2 2


Output

3
2

Solution (in PYTHON3):

Solution:
import sys;

def init(n_):
    length = 1;
    while(length < n_):
        length*=2
    element = [0]*(2*length-1)
    for i in range(2*length-1):
        element[i] = 0
    return element,length

def update(k,a,element):
    k+=n-1
    element[k]+=a
    while(k > 0):
        k = (int)((k-1)/2)
        element[k] = element[k*2+1]+element[k*2+2]

def findmin(a, b):
    return findquery(a,b+1,0,0,n)

def findquery(a, b, k, l, r):
    if(r <= a or b <= l):
        return 0
    if(a <= l and r <= b):
        return element[k]

    vl = findquery(a,b,k*2+1,l,(int)((l+r)/2+0.5))
    vr = findquery(a,b,k*2+2,(int)((l+r)/2),r)
    return vl+vr

n,q = map(int, input().split());

element,n = init(n)

for i in range(q):
    query,key,value = map(int, input().split());
    if(query == 0):
        update(key-1,value,element)
    else :
        print(findmin(key-1,value-1))