Farmer John đang cố thuê các nhà thầu giúp sắp xếp lại trang trại, nhưng đến nay tất cả đều bỏ việc khi nhìn thấy chuỗi chỉ dẫn phức tạp mà FJ muốn họ làm theo. Phải tự mình hoàn thành dự án, ông nhận ra rằng quả thật mình có lẽ đã khiến dự án phức tạp hơn mức cần thiết. Hãy giúp ông làm theo các chỉ dẫn để hoàn tất việc nâng cấp trang trại.

Trang trại của FJ gồm \(N\) cánh đồng nằm thành một hàng, được đánh số thuận tiện từ \(1\ldots N\). Mỗi cánh đồng có thể chứa một số lượng kiện cỏ khô bất kỳ. Các chỉ dẫn của Farmer John gồm ba loại:

1. Với một đoạn cánh đồng liên tiếp cho trước, thêm một kiện cỏ khô mới vào mỗi cánh đồng.
2. Với một đoạn cánh đồng liên tiếp cho trước, xác định số kiện cỏ khô nhỏ nhất trong một cánh đồng thuộc đoạn đó.
3. Với một đoạn cánh đồng liên tiếp cho trước, đếm tổng số kiện cỏ khô bên trong đoạn đó.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên dương \(N\) (\(1\le N\le200\,000\)) và \(Q\) (\(1\le Q\le100\,000\)).

Dòng tiếp theo chứa \(N\) số nguyên không âm, mỗi số không vượt quá \(100\,000\), cho biết số kiện cỏ khô ban đầu trong mỗi cánh đồng.

Mỗi dòng trong \(Q\) dòng tiếp theo chứa một chữ cái in hoa M, P hoặc S, tiếp theo là hai số nguyên dương \(A\) và \(B\) (\(1\le A\le B\le N\)), hoặc ba số nguyên dương \(A\), \(B\) và \(C\) (\(1\le A\le B\le N\); \(1\le C\le100\,000\)). Có ba số nguyên khi và chỉ khi chữ cái in hoa là P.

Nếu chữ cái là M, in số kiện cỏ khô nhỏ nhất trong đoạn cánh đồng từ \(A\ldots B\).

Nếu chữ cái là P, đặt thêm \(C\) kiện cỏ khô vào mỗi cánh đồng trong đoạn từ \(A\ldots B\).

Nếu chữ cái là S, in tổng số kiện cỏ khô trong đoạn cánh đồng từ \(A\ldots B\).

Dữ liệu ra

Với mỗi chỉ dẫn M hoặc S của FJ, in một dòng kết quả tương ứng.

Ví dụ

4 5
3 1 2 4
M 3 4
S 1 3
P 2 3 1
M 3 4
S 1 3

2
6
3
8

Nguồn

USACO 2015 December Contest, Platinum - Counting Haybales: https://usaco.org/index.php?page=viewproblem2&cpid=578

Tác giả: Nick Wu.