Mô tả và yêu cầu

(Thời gian chạy 2s)
Nam tham gia một cuộc thi có bài toán như sau: Ban tổ chức chuẩn bị N
cái hộp được đánh số từ 1 đến N. Cái hộp thứ i có giá trị điểm là A[i]. Nam được
quyền chọn một dãy các cái hộp liên tiếp và điểm của cậu sẽ là tổng giá trị điểm
của các hộp trong dãy đó (biết giá trị điểm có thể âm). Nhưng mọi chuyện không
đơn giản như vậy, khi vào cuộc thi Ban tổ chức đã đưa ra những đoạn [L, R] (1 ≤
L ≤ R ≤ N) và yêu cầu Nam chỉ được chọn các hộp trong đoạn [L, R] đó (tức l à
Nam chỉ được quyền chọn 1 dãy các hộp liên tiếp bắt đầu từ X và kết thúc tại Y
sao cho L ≤ X ≤ Y ≤ R). Không những vậy họ còn có thể tăng giá trị điểm của
một hộp X bất kì lên một lượng W. Đây là bài toán quá khó với Nam, bạn hãy
giúp Nam tìm số điểm lớn nhất có thể đạt được với mỗi yêu cầu của Ban tổ chức.

Dữ liệu vào

- Dòng đầu tiên là hai số nguyên dương N và Q là số thao tác của ban tổ
chức (N, Q ≤ 5*104).
- Dòng thứ hai gồm N số nguyên A[i] (|A[i]| ≤ 109).
- Q dòng tiếp theo mỗi dòng gồm:
+ Một số T là loại thao tác (Nếu T bằng 1 nghĩa là ban ban tổ chức đang
đặt ra 1 đoạn [L, R] và yêu cầu Nam trả lời, ngược lại nếu T = 2 thì nghĩa là họ
quyết định tăng giá trị điểm của một hộp X lên W).
+ Nếu T = 1, nhập vào 2 số nguyên dương L, R (1 ≤ L ≤ R ≤ N).
+ Ngược lại nếu T = 2, nhập vào 1 số nguyên dương X (1 ≤ X ≤ N) và một
số nguyên W (|W| ≤ 109).
Output: Gồm Q dòng với mỗi dòng là số điểm lớn nhất có thể đạt được
với mỗi đoạn [L, R] tương ứng.

Ví dụ

Input                               Output
              10 4                                6
              3 -2 1 4 -5 8 -10 5 -2 6            8
              1 1 5                               8
              2 5 -1
              1 4 9
              1 2 7