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:
"""Range Minimum Query (RMQ)"""
# 丁寧に実装する


# 配列のidx番目の要素の値をxに変更する, 1点更新
def update(idx, x):
    idx += size-1  # 配列のidx番目の要素に対応するseg木のノードのindex
    seg[idx] += x  # 対象のノードの値を更新する
    # 親のノードの値も更新する
    while idx > 0:
        idx = (idx-1)//2  # ノードidxの親のindex, いつか0になる
        seg[idx] = seg[2*idx+1] + seg[2*idx+2]  # 左右の子を見てminを計算する
    # 根ノードであるノード0まで修正したのでreturnする
    return


# この関数は半開区間[a, b)に対するクエリについて最小値を答えるもの
def query(a, b, k, l, r):  # 半開区間[a, b)に対するクエリについて、ノードk(担当している半開区間[l, r))が答える
    # 最初は根に質問を飛ばしている
    if r <= a or b <= l:  # ノードkの担当区間は[l, r)であり、この条件を満たすときは求めたい区間[a, b)と範囲が全く被っていない
        return INF  # 区間が被らない場合は単位元(minの単位元はINF)
    if a <= l and r <= b:
        return seg[k]  # ノードkの担当範囲が求めたい区間[a, b)に完全に含まれる場合はそのノードも持っている値をそのまま返す
    else:
        # 一部だけ範囲が被るような場合は左右の子に委託する
        c1 = query(a, b, 2*k+1, l, (l+r)//2)  # 左の子に値を聞く
        c2 = query(a, b, 2*k+2, (l+r)//2, r)  # 右の子に値を聞く
        return c1 + c2  # 左右の子のminを取る


N, Q = map(int, input().split())  # 配列のサイズ(管理したい要素の数), クエリの個数
size = 1  # seg木の葉の個数
while N > size:
    size *= 2  # seg木の葉の個数を計算する, N以上の最小の2冪数, 末端に来る葉の数が2の冪数でないと、seg木の構造がおかしくなる

# 単位元
# INF = float('inf')
INF = 0  # 今回の問題設定
# seg木を単位元で初期化する
seg = [INF]*(2*size-1)

for _ in range(Q):
    com, x, y = map(int, input().split())
    if com == 0:
        x -= 1
        update(x, y)
    else:
        x -= 1
        y -= 1
        print(query(x, y+1, 0, 0, size))  # ノード0(担当している半開区間[0, size))にクエリを投げる
        # y+1としているのは、半開区間とかの関係