Array of n integers is given. Find the sum of elements on a segment.
The first line contains two integers n and k (1≤n≤105,0≤k≤105) — the number of elements in array and number of queries. 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.
For each query of type Q l r print the sum of elements on a segment [l;r].