Biến đổi bí ẩn 2

Bạn được trao một dãy số nguyên dương gồm \(N\) phần tử, được ký hiệu là \(A_1, A_2, \dots, A_N\). Dãy số này đang trải qua những biến động kỳ lạ, và bạn là người duy nhất có thể theo dõi toàn bộ quá trình.

Có tất cả \(Q\) thao tác được thực hiện lên dãy số theo thứ tự, và mỗi thao tác sẽ có một trong hai dạng sau:

• Loại 1: 1 u v x --- Tăng giá trị của tất cả phần tử trong đoạn từ \(A_u\) đến \(A_v\) thêm \(x\) đơn vị.
• Loại 2: 2 u v --- Hỏi xem trong đoạn từ \(A_u\) đến \(A_v\) thì phần tử lớn nhất là bao nhiêu.

Hãy giúp trả lời tất cả các truy vấn loại 2.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)) --- số phần tử trong dãy và số thao tác cần thực hiện.
• Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)).

• \(Q\) dòng tiếp theo, mỗi dòng mô tả một thao tác như sau:

• Dạng 1 $u$ $v$ $x$ với \(1 \le u \le v \le N\) và \(1 \le x \le 10^9\): tăng tất cả các phần tử từ vị trí \(u\) đến \(v\) lên \(x\).

• Dạng 2 $u$ $v$ với \(1 \le u \le v \le N\): truy vấn giá trị lớn nhất trong đoạn từ \(u\) đến \(v\).

Output

Với mỗi truy vấn loại 2, in ra một dòng chứa kết quả tương ứng.

Example

5 4
2 6 3 5 8
1 2 5 3
2 1 4
1 3 4 2
2 3 5

9
11

Scoring

• Subtask 1 (30%): \(N \le 10^3\), \(Q \le 10^3\).
• Subtask 2 (20%): \(N \le 10^5\), \(Q \le 10^5\), chỉ chứa thao tác loại 2.
• Subtask 3 (20%): \(N \le 10^5\), \(Q \le 10^5\), tất cả thao tác loại 1 đều xuất hiện trước các thao tác loại 2.
• Subtask 4 (30%): \(N \le 10^5\), \(Q \le 10^5\), không giới hạn gì thêm.