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, \ldots, 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