Biến đổi bí ẩn

Bạn được trao quyền điều khiển một dãy số kỳ lạ gồm \(n\) phần tử, ban đầu tất cả các giá trị đều bằng \(0\). Tuy nhiên, một thế lực bí ẩn đã bắt đầu can thiệp vào dãy số này thông qua một chuỗi gồm \(m\) phép biến đổi.

Mỗi phép biến đổi có thể là một trong hai loại sau:

• Loại 0: Tăng mỗi phần tử trong đoạn từ chỉ số \(u\) đến \(v\) thêm \(k\) đơn vị.
• Loại 1: Truy vấn giá trị lớn nhất trong đoạn từ chỉ số \(u\) đến \(v\).

Bạn cần thực hiện chính xác các thao tác này và trả lời kết quả tương ứng cho mỗi truy vấn loại 1.

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\) (\(1 \le n \le 50000\), \(1 \le m \le 10^5\)) --- số lượng phần tử của dãy và số thao tác cần thực hiện.

Tiếp theo là \(m\) dòng, mỗi dòng biểu diễn một thao tác, có thể có một trong hai dạng sau:

• 0 u v k: Tăng mỗi phần tử trong đoạn \([u, v]\) thêm \(k\) đơn vị (\(1 \le u \le v \le n\), \(0 < k\)).
• 1 u v: Truy vấn giá trị lớn nhất trong đoạn \([u, v]\) (\(1 \le u \le v \le n\)).

Đảm bảo rằng giá trị của bất kỳ phần tử nào trong dãy sẽ không vượt quá \(2^{31} - 1\) tại bất kỳ thời điểm nào.

Output

Với mỗi truy vấn loại 1, in ra một dòng chứa giá trị lớn nhất trong đoạn tương ứng.

Example

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

4