Quân là một tay cưa gái khét tiếng ở xứ sở Hà Nội Cánh Tay. Cưa gái nhiều nên đã quá ngán, cậu bèn chuyển qua cưa cây.

Hàng cây gồm ~n~ cây, được đánh số từ ~1~ đến ~n~ từ trái qua phải. Ở vị trí thứ ~i~, Quân chỉ được phép trồng cây có độ cao không quá ~h_i~.

Quân muốn tìm một loại cây có độ cao là số nguyên ~H~ ~(H \le h_1, H \le h_n)~ và trồng vào một số vị trí thích hợp, biết rằng cậu chắc chắn sẽ trồng cây vào vị trí thứ ~1~ và thứ ~n~.

Nếu cây ở vị trí thứ ~i~ bị đổ, nó sẽ làm các cây ở vị trí trong khoảng ~[i+1, i+H]~ đổ theo.

Hãy giúp Quân tính xem, độ cao ~H~ nhỏ nhất có thể là bao nhiêu, sao cho nếu Quân chặt đổ cây ở vị trí thứ ~1~ thì cây ở vị trí thứ ~n~ cũng bị đổ theo.

Input

• Dòng đầu tiên chứa một số nguyên dương ~n~ ~(n \leq 10^7)~.
• Dòng thứ hai chứa ~n~ số nguyên không âm ~h_1, h_2, \ldots, h_n~ ~(h_i \leq n)~.

Dữ liệu bảo đảm tồn tại một đáp án hợp lệ.

Output

• In ra một số nguyên dương là kết quả của bài toán.

Subtask

• Subtask ~1~ (~20\%~ số điểm): ~n \le 100~.
• Subtask ~2~ (~20\%~ số điểm): ~n \le 1000~.
• Subtask ~3~ (~20\%~ số điểm): ~n \le 10^5~.
• Subtask ~4~ (~20\%~ số điểm): ~n \le 10^6~.
• Subtask ~5~ (~20\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

10 
10 1 2 0 3 4 5 0 2 10

Sample Output 1

2

Explanation 1

Quân trồng cây độ cao ~2~ ở các vị trí ~1, 3, 5, 7, 9, 10~.

Cho ma trận vuông ~n \times n~, các hàng được đánh số từ ~1~ tới ~n~, các cột được đánh số từ ~1~ tới ~n~. Các ô được sắp xếp theo thứ tự từ trái sang phải, từ trên xuống dưới, ô ~(i,j)~ có giá trị là ~a_{i,j}~.

Ivan Tèo đang đứng ở ô ~(1,1)~ của ma trận, trong mỗi lần đi, cậu chỉ có thể đi sang phải hoặc xuống dưới, nói cách khác, nếu đang ở ô ~(i,j)~, cậu chỉ có thể đi sang ô ~(i+1,j)~ hoặc ~(i,j+1)~. Gọi ~Best(i,j)~ là giá trị lớn nhất có thể nếu Ivan Tèo đi từ ô ~(1,1)~ tới ô ~(i,j)~. Vì cảm thấy rằng nếu chỉ hỏi các ~Best(i,j)~ thì quả là nhàm chán và không đánh giá đúng được tiềm năng của Tèo, ~mrhee~ quyết định tạo ra một giá trị mới như sau:

• Gọi ~S~ là tổng các ~Best(i,j)~ của mọi ô ~(i,j)~ trên ma trận.
• Nói cách khác, ~S = \sum Best(i,j)~, với mọi ~(1 \le i,j \le n)~.

Vì lại cảm thấy việc in ra ~S~ của ma trận hiện tại là quá dễ với Tèo, ~mrhee~ quyết định tạo ra ~q~ sự thay đổi, sự thay đổi thứ ~i~ có dạng như sau:

• Cho ba số nguyên ~u_i,v_i,delta_i~ ~(1 \le u_i,v_i \le n, -1\le delta_i \le 1)~, tức gán giá trị ~a_{u_i,v_i} = a_{u_i,v_i} + delta_i~.
• Sau mỗi truy vấn, hãy in ra giá trị ~S~ của ma trận mới.

Input

• Dòng đầu tiên gồm hai số nguyên dương ~n,q~ ~(1 \le n \le 1000, 1 \le q \le 3 \times 10^4)~
• ~n~ dòng sau, dòng thứ ~i~ gồm ~n~ số nguyên, số thứ ~j~ miêu tả giá trị ~a_{i,j}~ ~(-10^2 \le a_{i,j} \le 10^2)~ của ma trận.
• ~q~ dòng tiếp theo, mỗi dòng gồm ba số nguyên ~u_i,v_i,delta_i~ ~(1 \le u_i,v_i \le n, -1 \le delta_i \le 1)~ miêu tả truy vấn thứ ~i~.

Output:

• Gồm một dòng in ra số cặp ~(i,j)~ thỏa mãn.

Subtask:

• Subtask ~1~ (~25\%~ số điểm): ~q \le 10~.
• Subtask ~2~ (~25\%~ số điểm): Ô ~(u_i,v_i)~ trong mọi truy vấn là giống nhau và ~q \le 3000~, đồng thời ~delta_i = 1~ với mọi truy vấn.
• Subtask ~3~ (~30\%~ số điểm): ~q \le 3000~
• Subtask ~4~ (~20\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

2 2
1 2
2 2
1 2 0
2 1 1

Sample Output 1

12
14

Sample Input 2

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

Sample Output 2

196
195
203
199

Explanation

Ở ví dụ ~1~, sau truy vấn đầu, bảng không thay đổi gì, ta có các ~Best(i,j)~ như sau:

• ~Best(1,1) = 1~
• ~Best(1,2) = 3~
• ~Best(2,1) = 3~
• ~Best(2,2) = 5~

Sau khi tăng ô ~(2,1)~ lên ~4~ đơn vị, ta có:

• ~Best(1,1) = 1~
• ~Best(1,2) = 3~
• ~Best(2,1) = 4~
• ~Best(2,2) = 6~

Cho dãy số nguyên dương ~𝐴~ có ~𝑁~ phần tử ~𝑎_1, 𝑎_2, … , 𝑎_N~. Có ~𝑄~ truy vấn có dạng ~𝐿, 𝑅, 𝐾~ với ý nghĩa như sau:

• Xét dãy con ~𝐵~ là dãy con của ~𝐴~ gồm các phần tử liên tiếp từ vị trí ~𝐿~ đến vị trí ~𝑅~ : ~𝑎_L, 𝑎_{L+1}, … , a_R~ ~(1 ≤ 𝐿 ≤ 𝑅 ≤ 𝑁)~, ta xây dựng dãy số ~𝐶~ bằng cách coi ~𝐶~ là tập hợp tất cả các dãy con liên tiếp của ~B~. Ví dụ: dãy ~𝐵 = \{1, 2, 1\}~ các dãy con của ~B~ là ~\{1\}, \{2\}, \{1\}, \{1,2\}, \{2,1\}, \{1,2,1\}~ ta sẽ có dãy ~𝐶 = \{1, 2, 1, 1, 2, 2,1, 1,~~ 2, 1\};~
• Sắp xếp dãy ~𝐶~ theo thứ tự không giảm và đưa ra phần tử thứ ~𝐾~. Ví dụ: với dãy ~𝐶~ trên ta sắp xếp thành ~\{1, 1, 1, 1, 1, 1, 2, 2, 2, 2\}~ và phần tử thứ ~8~ là ~2~.

Yêu cầu: Cho dãy số ~𝐴~ và ~𝑄~ truy vấn như trên, hãy đưa ra kết quả phần tử thứ ~𝐾~ của dãy số ~𝐶~ tương ứng trong mỗi truy vấn.

Dữ liệu nhập vào từ file văn bản DLT.INP:

• Dòng đầu tiên gồm hai số nguyên dương ~𝑁~ và ~𝑄~ ~(1 ≤ 𝑁, 𝑄 ≤ 5 \times 10^5)~ là số phần tử của dãy số ~𝐴~ và số lượng truy vấn~;~
• Dòng thứ hai gồm ~𝑁~ số nguyên dương ~𝑎_1, 𝑎_2, … , 𝑎_N~ ~(1 ≤ 𝑎_i ≤ 5 \times 10^5; \ 1 ≤ 𝑖 ≤ 𝑁);~
• ~𝑄~ dòng sau, mỗi dòng chứa ba số ~𝐿, 𝑅, 𝐾~ ~(1 ≤ 𝐿 ≤ 𝑅 ≤ 𝑁)~ mô tả truy vấn.

Dữ liệu đảm bảo đúng đắn, luôn có kết quả.

Kết quả ghi ra file văn bản DLT.OUT:

~𝑄~ dòng là kết quả tương ứng của mỗi truy vấn.

Ràng buộc

• Có ~20\%~ số test ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁, 𝑄 ≤ 100;~
• ~10\%~ số test khác ứng với ~10\%~ số điểm của bài thoả mãn: ~𝑁, 𝑎_i ≤ 100;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁, 𝑄, 𝑎_i ≤ 5000;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁, 𝑄 ≤ 10^5; 𝑎_i ≤ 100;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁, 𝑄, 𝑎_i ≤ 10^5;~
• ~10\%~ số test còn lại ứng với ~10\%~ số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

5 2
1 2 1 3 2
1 3 8
1 4 18

Output

2
3