Cho một mảng gồm N phần tử và Q truy vấn. Có 3 loại truy vấn:

• S i j: xuất ra tổng các phần tử có chỉ số từ i đến j
• U i p: tăng A[i] lên p đơn vị
• V i p: giảm A[i] đi p đơn vị

Dữ liệu nhập: Dòng đầu tiên chứa 2 số nguyên N, Q - số lượng phần tử của mảng và số lượng truy vấn. (1 ≤ Q ≤ 10⁵, 1 ≤ N ≤ 10⁶). Dòng thứ hai chứa N số nguyên là giá trị của mảng (1000 ≤ A_i ≤ 2000). Q dòng cuối cùng, mỗi dòng chứa một truy vấn, i, j, p được đảm bảo không có giá trị âm.

Dữ liệu xuất: tương ứng với mỗi truy vấn "S i j" xuất trên một dòng là kết quả tìm được.

Lưu ý: chỉ số mảng được bắt đầu từ 0.

Ví dụ:

Input:

5 3

1500 1501 1502 1503 1504

S 1 3

U 3 100

S 1 3

Output:

4506

4606