Given an array $A$ of size $N$, support the $Q$ of the following operations:

1. Find the sum of all elements from index $l$ to index $r$.
2. Update the element at index $i$ to value $x$.

Constraints

$1\le N,Q\le 2\times {10}^5$

$1\le l\le r\le N$

$1\le i\le N$

$1\le A_i,x\le {10}^9$

Input Specification

The first line contains $2$ integers $N$ and $Q$.

The second line contains $N$ integers $A_1,A_2,\dots ,A_N$, the initial elements of $A$.

The next $Q$ lines are one of two forms:

1. S l r representing the first operation.
2. U i x representing the second operation.

Output Specification

For each type $1$ operation output one integer on its own line, the answer to that query.

Sample Input

5 5
1 2 3 4 5
S 2 4
S 1 5
U 2 6
S 2 2
S 2 4

Sample Output

9
15
6
13