eolymp
Competitions

Дерево Фенвика

Sum on a segment

Array of n integers is given. Find the sum of elements on a segment.

Input

The first line contains two integers n and k - the number of elements in array and number of queries (1n105, 0k105). Next k lines contain the queries of two types:

  • A i x - assign to the i-th element the value of x (1in, 0x109);
  • Q l r - find the sum of numbers in array at positions from l to r (1lrn).

Initially the array contains zeros.

Output

For each query of type Q l r print the sum of elements on a segment [l; r].

Time limit 1 second
Memory limit 128 MiB
Input example #1
5 9
A 2 2
A 3 1
A 4 2
Q 1 1
Q 2 2
Q 3 3
Q 4 4
Q 5 5
Q 1 5
Output example #1
0
2
1
2
0
5