Tách đoạn

Cho dãy gồm \(n\) số \(a_1, a_2, \ldots, a_n\). Độ lệch của dãy số là hiệu của phần tử lớn nhất và nhỏ nhất trong dãy số. Hãy chia, tách dãy số ban đầu thành các đoạn con liên tiếp tùy ý sao cho tổng độ lệch của tất cả các đoạn con là lớn nhất.

Vấn đề trên khá đơn giản, nên để cho bài toán trở nên khó khăn hơn, người ta đã đưa vào \(Q\) phép biến đổi dãy số ban đầu. Mỗi phép biến đổi cho bởi bộ ba số \(L, R, x\) có nghĩa là tăng các phần tử của dãy có chỉ số từ \(L\) đến \(R\) lên một lượng \(x\).

Sau mỗi phép biến đổi, hãy tính tổng độ lệch lớn nhất.

Input

• Dòng đầu ghi \(2\) số \(n, Q\) (\(1 \le n, Q \le 10^5\)) là số phần tử của dãy và số phép biến đổi.

• Dòng tiếp theo ghi \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(0 \le a_i \le 10^6\)).

• Trong \(Q\) dòng tiếp theo, mỗi dòng ghi \(3\) số \(L, R, x\) (\(1 \le L \le R \le n\); \(0 \le x \le 10^6\)) thể hiện một phép biến đổi.

Ràng buộc:

• Có \(30\%\) số test ứng với \(30\%\) số điểm có \(1 \le n, Q \le 200\);

• Có \(40\%\) số test ứng với \(40\%\) số điểm có \(1 \le n, Q \le 3000\);

• Có \(30\%\) số test ứng với \(30\%\) số điểm có \(1 \le n, Q \le 10^5\).

Output

Ghi ra \(Q\) câu trả lời là tổng độ lệch của dãy số sau mỗi phép biến đổi. Mỗi số trên một dòng tương ứng.

Example

Input:

4 3
1 2 3 4
1 2 1
1 1 2
2 3 1

Output:

2
2
0

Note

Sau phép biến đổi đầu tiên dãy là \(2, 3, 3, 4\). Tổng độ lệch lớn nhất khi chia thành \(1\) đoạn là \(4 - 2 = 2\) (chia thành \(\{2, 3\}, \{3, 4\}\) cũng được \(1 + 1 = 2\)).

Sau phép biến đổi thứ hai dãy là \(4, 3, 3, 4\). Tổng độ lệch lớn nhất khi chia thành \(\{4, 3\}\) và \(\{3, 4\}\) là \(1 + 1 = 2\) (nếu để cả dãy làm một đoạn thì độ lệch chỉ là \(1\)).

Sau phép biến đổi thứ ba dãy là \(4, 4, 4, 4\). Mọi cách chia đều có độ lệch bằng \(0\).