Chia dãy

Alice có một dãy số gồm $n$ phần tử $A=(a_1,a_2,\dots ,a_n)$. Alice muốn chia dãy $A$ thành một số đoạn con liên tiếp sao cho tổng giá trị mỗi đoạn con là lớn nhất. Giá trị của một đoạn con được định nghĩa là hiệu số giữa phần tử lớn nhất và phần tử nhỏ nhất trong đoạn con đó.

Alice cần xử lí $Q$ thao tác thuộc một trong hai loại sau:

1. Loại 1 có dạng 1 l r x, nghĩa là gán $a_i=a_i+x$ với mọi $l\le i\le r$.
2. Loại 2 có dạng 2 l r, nghĩa là tìm cách chia dãy gồm các phần tử từ $l$ đến $r$ của dãy $A$ thành các đoạn con liên tiếp sao cho tổng giá trị là lớn nhất có thể.

Với mỗi thao tác loại 2 hãy đưa ra tổng giá trị lớn nhất khi chia.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên dương $n,Q$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• $Q$ dòng tiếp theo, mỗi dòng chứa một trong hai loại thao tác như mô tả ở trên.

Dữ liệu ra

• Gồm nhiều dòng, mỗi dòng ghi một số là tổng giá trị lớn nhất tương ứng khi thực hiện thao tác loại 2.

Ràng buộc

• $1\le n,Q\le 2\times {10}^5$
• $|a_i|\le {10}^6$
• Trong tất cả các thao tác: $1\le l\le r\le n$ và $|x|\le {10}^6$.
• Subtask 1 (25%): $n\le 20$; $Q=1$.
• Subtask 2 (25%): $n,Q\le 200$.
• Subtask 3 (25%): $n,Q\le 3000$.
• Subtask 4 (25%): Không có ràng buộc nào thêm.

Ví dụ

Ghi chú

Một đoạn con chỉ gồm một phần tử có giá trị bằng $0$. Có thể chia thành các đoạn tùy ý (kể cả mỗi phần tử một đoạn).