Simple Sum

Input

The first line of input consists of two integers, $N$ and $K$, representing the number of elements in the array and the number of queries, respectively. (1 \leq N \leq 10^6); (1 \leq K \leq 10^5). The next $K$ lines contain the queries, which are of two types:

1. A $i$ $x$ – Set the $i$-th element of the array to the value $x$ (1 \leq i \leq N; 0 \leq x \leq 10^9).

2. Q $l$ $r$ – Calculate the sum of the elements in the array from position $l$ to $r$. (1 \leq l \leq r \leq N).

Initially, all elements of the array are zero.

Output

For each query of the form Q $l$ $r$, output a single number representing the sum of the elements in the specified segment.

Examples