Cho một dãy gồm \(n\) phần tử có giá trị ban đầu bằng \(0\).

Cần thực hiện \(m\) thao tác thuộc hai loại:

• Tăng giá trị của mỗi phần tử trong một đoạn con liên tiếp lên vài đơn vị.
• Tìm giá trị lớn nhất trong đoạn con bất kỳ

Input

• Dòng đầu tiên: Chứa hai số \(n,m\) \((1 \le n \le 50000, 1 \le m \le 10^5)\)
• \(m\) dòng tiếp theo, mỗi dòng có thể có một trong hai định dạng sau:
• 0 u v k: Tăng mỗi phần tử từ vị trí \(u\) đến vị trí \(v\) lên \(k\) đơn vị \((1 \le u \le v \le n, 0 < k)\)
• 1 u v: Cho biết giá trị lớn nhất thuộc đoạn \([u, v]\) là bao nhiêu?

Dữ liệu vào đảm bảo giá trị của một phần tử không bao giờ vượt quá \(2^{31}-1\)

Output

• Với mỗi câu hỏi, ghi ra đáp án trên từng dòng

Example

6 3
0 1 3 3
0 4 6 4
1 1 6

4