题目描述

单点改 + 区间和 给定一个长度为 n(0≤n≤10^5 )，初始值都为 0 的序列，x(0≤x≤10^5 ) 次的修改某些位置上的数字， 每次加上一个数，并在此期间提出 y(0≤y≤10^5 ) 个问题，求每段区间的和。

输入格式

第一行 1 个整数，表示序列的长度 n。 第二行 1 个整数，表示操作的次数 w(0≤w≤2×10^5)。 后面依次是 w 行，分别表示加入和询问操作。 其中，加入用 x 表示，询问用 y 表示。 x 的格式为 x a b 表示在序列上第 a 个数加上 b。保证 1≤a≤n，1≤b≤10^9 。 y 的格式为 y a b 表示询问 a 到 b 区间的加和。保证 1≤a≤b≤n。

输出格式

每行一个正整数，分别是每次询问的结果。

样例

输入样例 1

5
4
x 3 8
y 1 3
x 4 9
y 3 4

输出样例 1

8
17

输入样例 2

1 3
x 1 100
q 1 1
q 1 1

输出样例 2

100
100

输入样例 3

5 6
x 1 10
x 2 -3
q 1 2
x 3 7
q 2 3
q 1 5

输出样例 3

7
4
14