Paula rất thích nấu ăn, và để chuẩn bị một món ăn ngon thì Paula phải cắt một dãy số gồm ~n~ số nguyên ra các đoạn với tổng giá trị lớn nhất.

Giá trị của một đoạn được định nghĩa là hiệu giữa phần tử lớn nhất và bé nhất trong đoạn. Giá trị của một dãy đã được cắt là tổng giá trị của các đoạn.

Ví dụ, chúng ta cắt dãy ~[1,4,1,5,3,6]~ thành 2 dãy con ~[1, 4, 1]~ và ~[5, 3, 6]~ thì giá trị của dãy sẽ là ~(4-1)+(6-3)=6~

Sẽ có ~q~ truy vấn có dạng "thêm ~x~ vào các phần tử có số thứ tự ~l,l+1,...,r~". Sau mỗi truy vấn, trả lời câu hỏi "Giá trị lớn nhất có thể của dãy là bao nhiêu?"

Input

Dòng đầu tiên gồm số nguyên ~n~ và ~q~ ~(1 \le n,q \le 200000)~, độ dài của dãy và số truy vấn.

Dòng thứ hai gồm n số nguyên ~a_i~ ~(-10^8 \le a_i \le 10^8)~, dãy số Paula cần cắt.

Mỗi trong ~q~ dòng tiếp theo gồm 2 số nguyên ~l,r~ ~(1 \le l \le r \le n)~ và ~x~ ~(-10^8 \le x \le 10^8)~, mô tả một truy vấn.

Output

In ra ~q~ dòng, là đáp án sau mỗi truy vấn.

Sample 1

Input

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

Output

2
2
0

Sample 2

Input

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

Output

2
1
3

Giải thích Sample 1

Cách cắt tối ưu sau các lần update lần lượt là ~[2,3,3,4] , [4,3] [3,4] , [4, 4, 4, 4]~

Subtask

• ~8~ test đầu có ~1 \le n,q \le 200~
• ~6~ test tiếp theo có ~1 \le n,q \le 3000~
• ~6~ test còn lại không có điều kiện gì thêm