Bài tập

\begincenter

\endcenter

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.

Có \(n\) người xếp thành một hàng dọc, người thứ \(i\) có chiều cao \(h_i\). Với mỗi người trong hàng, hãy tìm vị trí của người gần nhất về phía bên trái có chiều cao lớn hơn người đó.

Input

• Dòng đầu tiên chứa số nguyên \(n\): số lượng người trong hàng.
• Dòng thứ hai chứa \(n\) số nguyên \(h_1, h_2, \ldots, h_n\): chiều cao của từng người.
• \(1 \leq n \leq 2 \cdot 10^5\)
• \(1 \leq h_i \leq 10^9\)

Output

In ra \(n\) số nguyên, số thứ \(i\) là vị trí của người gần nhất bên trái có chiều cao lớn hơn người thứ \(i\). Nếu không có người nào như vậy, in ra \(0\).

Example

8
2 5 1 4 8 3 2 5

0 0 2 2 0 5 6 5 

Thành oai hùng ngày nào nay đã trở thành bảo vệ của rừng BaNgocLand(có dạng hình chữ nhật kích thước \(m \times n\)). Để đền đáp công lao to lớn của Thành, Chúa đất cho phép anh chọn một vùng đất hình chữ nhật có kích thước \(k \times k\), có các cạnh song song với các bìa rừng, khai thác tài nguyên tại vùng đất này để lây kinh phí dựng nhà, lấy vợ.

Chúa đất chỉ cho phép anh khai thác cây trong đúng vùng đất mà anh ấy chọn. Biết giá trị của mỗi cây trong khu rừng AnLuuLand tại vị trí dòng \(i\) cột \(j\) là \(a_{i, j}\) nguyên. Bạn hãy giúp Thành chọn một vùng đất có giá trị cao nhất mà vẫn thỏa mãn yêu cầu của Chúa đất. Thành có thể không chọn nếu muốn.

Input

Dòng 1: Gồm \(3\) số nguyên dương \(m, n, k\) \((m, n, k \leq 700)\).

\(m\) dòng sau, mỗi dòng gồm \(n\) số nguyên là giá trị của mỗi cây trong khu rừng. Giá trị của mỗi cây là một số nguyên có trị tuyệt đối không quá \(10^9\).

Output

Một số duy nhất là giá trị cao nhất mà Thành có thể nhận được.

Example

4 5 2
1 1 2 0 0
1 2 1 0 1
4 3 5 1 1
1 5 5 0 0

18