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, có 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, có 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\) sao cho tổng giá trị là lớn nhất có thể.

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

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, Q\) (\(n, Q \le 2 \cdot 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^6\)).
• \(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. Trong tất cả các thao tác \(1 \le l \le r \le n\) và \(|x| \le 10^6\).

Output

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

Example

4 3
1 2 3 4
2 1 4
1 1 1 2
2 1 4

3
2

Ràng buộc

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