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(1\le n\le 10^5,0\le k\le 10^5)$ — 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\le i\le n,0\le x\le 10^9)$;

• Q l r — find the sum of numbers in array at positions from $l$ to $r(1\le l\le r\le n)$.

Initially the array contains zeros.

Output

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

Examples