Potentiometers

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

There are $N$ potentiometers arranged from $1$ to $N$. Each value is a resistance in Ohms, and the resistance of a contiguous series is the sum of its values. Process point assignments and range measurements.

Input

• The first line contains $N$ and $Q$: the number of potentiometers and operations.
• The second line contains $N$ initial resistances, each from $0$ to $1000$.
• Each of the next $Q$ lines is S x r, which sets position $x$ to $r$, or M x y, which asks for the sum from $x$ through $y$, where $1 \le x \le y \le N$.

Output

For every M operation, print the measured range sum.

Subtasks

• Subtask 1 — 20%: $1 \le N,Q \le 1000$.
• Subtask 2 — 30%: $1 \le N,Q \le 50000$.
• Subtask 3 — 50%: $1 \le N,Q \le 200000$.

Examples

Input

3 6
100 100 100
M 1 1
M 1 3
S 2 200
M 1 2
S 3 0
M 2 3

Output

100
300
300
200

Explanation

The three initial values are all $100$. The first two measurements are $100$ and $300$. After setting position $2$ to $200$, the sum on $[1,2]$ is $100+200=300$. After setting position $3$ to $0$, the sum on $[2,3]$ is $200+0=200$.