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 (1 ≤ n ≤ 105, 0 ≤ k ≤ 105). Next k lines contain the queries of two types:

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

Initially the array contains zeros.

Output

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