Range Sum Live Updates

Range Sum Live Updates

You are given an array of n integers (1-indexed) and must process q queries of two kinds: ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​‌​​​‌‌​‌​‌​​‌‌‌​​‌​‌‌​​‌​‌​‌‌​​​​‌​‌‌​​‌​‌​‌‌​​​‌​​‌‌​​‌‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌​​​‌‌‌​​‌​​‌‌‌​​‌​​‌‌​​​​​​‌‌​​‌‌​​‌‌​​​‌- U i v — set a[i] = v

• Q l r — output the sum a[l] + a[l+1] + ... + a[r]

Process the queries in order, printing the answer to every Q query on its own line (in order).

Input

Line 1: two integers n q (1 ≤ n, q ≤ 2·10^5) ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​‌​​​‌‌​‌​‌​​‌‌‌​​‌​‌‌​​‌​‌​‌‌​​​​‌​‌‌​​‌​‌​‌‌​​​‌​​‌‌​​‌‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌​​​‌‌‌​​‌​​‌‌‌​​‌​​‌‌​​​​​​‌‌​​‌‌​​‌‌​​​‌Line 2: n integers, the initial array (-10^9 ≤ a_i ≤ 10^9) Next q lines: a query in one of the two forms above (1 ≤ i, l, r ≤ n, l ≤ r, -10^9 ≤ v ≤ 10^9)

Output

One line per Q query, with the requested sum.

Example

Input: ​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​‌​​​‌‌​‌​‌​​‌‌‌​​‌​‌‌​​‌​‌​‌‌​​​​‌​‌‌​​‌​‌​‌‌​​​‌​​‌‌​​‌‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌​​​‌‌‌​​‌​​‌‌‌​​‌​​‌‌​​​​​​‌‌​​‌‌​​‌‌​​​‌``` 5 3 1 2 3 4 5 Q 1 5 U 3 10 Q 1 5

Output:

15 22

### Constraints
- 1 ≤ n, q ≤ 2·10^5
​‌‌‌​‌​‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​‌‌​​​​‌​​‌‌‌​‌​​‌‌​​​‌‌​​‌‌‌‌​‌​‌‌​​​‌‌​‌‌​‌‌‌‌​‌‌​‌‌‌​​‌‌‌​‌​​​‌‌​​‌​‌​‌‌‌​​‌‌​‌‌‌​‌​​​​‌‌‌​‌​​‌‌‌​​​​​​‌‌‌‌​‌​‌‌​​​‌​​​‌‌​‌​‌​​‌‌‌​​‌​‌‌​​‌​‌​‌‌​​​​‌​‌‌​​‌​‌​‌‌​​​‌​​‌‌​​‌‌​​​‌‌‌​‌​​‌‌‌​‌​​​​‌‌‌‌​‌​​‌‌​​​‌​​‌‌​‌‌‌​​‌‌‌​​‌​​‌‌​​‌​​​‌‌‌​​​​​‌‌​​‌‌​​‌‌​‌‌‌​​‌‌​‌‌​​​‌‌‌​​‌​​‌‌‌​​‌​​‌‌​​​​​​‌‌​​‌‌​​‌‌​​​‌

4 2
10 10 10 10
Q 2 3
Q 1 4

20
40

5 3
1 2 3 4 5
Q 1 5
U 3 10
Q 1 5

15
22