Biến trở (Potentiometers)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ biến trở được xếp theo thứ tự từ $1$ đến $N$. Giá trị của mỗi biến trở là điện trở của nó, tính bằng Ohm. Tổng điện trở trên một đoạn liên tiếp bằng tổng các giá trị trong đoạn đó. Bạn cần xử lý các thao tác thay đổi một biến trở và đo tổng điện trở trên một đoạn.

Input

• Dòng đầu chứa hai số nguyên $N$ và $Q$: số biến trở và số thao tác.
• Dòng thứ hai chứa $N$ số nguyên là các điện trở ban đầu, mỗi giá trị từ $0$ đến $1000$.
• Mỗi trong $Q$ dòng tiếp theo là S x r để đặt biến trở $x$ thành $r$, hoặc M x y để đo tổng điện trở từ vị trí $x$ đến $y$, với $1 \le x \le y \le N$.

Output

Với mỗi thao tác M, in tổng điện trở trên đoạn tương ứng.

Subtask

• 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$.

Ví dụ

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

Giải thích

Ba biến trở ban đầu đều có giá trị $100$. Hai phép đo đầu cho $100$ và $300$. Sau khi đặt vị trí $2$ thành $200$, tổng trên $[1,2]$ là $100+200=300$. Cuối cùng đặt vị trí $3$ thành $0$, nên tổng trên $[2,3]$ là $200+0=200$.