Cho dãy \(a\) gồm \(n\) phần tử được đánh chỉ số từ \(1\) đến \(n\) và \(q\) truy vấn. Mỗi truy vấn thuộc một trong hai loại sau:

1. Tăng các phần tử từ chỉ số \(l\) đến \(r\) thêm \(x\).
2. Tìm giá trị lớn nhất của biểu thức \(a_{i_1} - a_{i_2} + a_{i_3} - a_{i_4} + \ldots\) với \(i_1, i_2, i_3, i_4, \ldots\) là các chỉ số được chọn thỏa mãn \(l \leq i_1 < i_2 < i_3 < i_4 < \ldots \leq r\). Nếu không chọn chỉ số nào thì giá trị của biểu thức là \(0\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \leq n, q \leq 10 ^ 5\)).
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(|a_i| \leq 10 ^ 9\)).
• Trong \(q\) dòng tiếp theo, mỗi dòng chứa số nguyên \(1\) hoặc \(2\). Số \(1\) theo sau bởi ba số nguyên \(l\), \(r\) và \(x\) (\(1 \leq l \leq r \leq n\), \(|x| \leq 10 ^ 9\)) mô tả truy vấn loại 1. Số \(2\) theo sau bởi hai số nguyên \(l\) và \(r\) (\(1 \leq l \leq r \leq n\)) mô tả truy vấn loại 2.

Output

• Với mỗi truy vấn loại 2, in ra giá trị lớn nhất của biểu thức trên một dòng.

Scoring

• Subtask 1 (30% số điểm): \(n, q \leq 20\).
• Subtask 2 (30% số điểm): \(n, q \leq 10 ^ 3\).
• Subtask 3 (30% số điểm): Truy vấn loại 1 có \(l = r\).
• Subtask 4 (10% số điểm): Không có ràng buộc gì thêm.

Example

5 5
9 3 -2 5 -1
2 1 3
1 4 5 6
2 2 5
1 2 2 -7
2 2 3

11
16
0