Паула любить готувати смажені страви. Щоб зробити страву якомога смачнішою, їй потрібно розрізати послідовність з ~n~ цілих чисел на сегменти з максимальною загальною вартістю.

Вартість сегмента - це різниця між його максимальним та мінімальним значенням. Вартість розрізаної послідовності - це сума вартостей усіх сегментів.

Наприклад, якщо ми розріжемо послідовність ~[1, 4, 1, 5, 3, 6]~ на сегменти ~[1, 4, 1]~ та ~[5, 3, 6]~, загальна вартість буде ~(4-1)+(6-3)=6~.

Буде ~q~ оновлень виду "додати ~x~ до елементів з індексами ~l, l+1, \ldots, r~". Після кожного оновлення дайте відповідь на запит "Яка максимально можлива вартість розрізаної послідовності?".

Input

Перший рядок містить цілі числа ~n~ та ~q~ ~(1 \leq n, q \leq 200000)~, довжину послідовності та кількість оновлень.

Другий рядок містить ~n~ цілих чисел ~a_i~ ~(-10^8 \leq a_i \leq 10^8)~, послідовність, яку Паула має розрізати.

Кожен з наступних ~q~ рядків містить цілі числа ~l~, ~r~ ~(1 \leq l \leq r \leq n)~ та ~x~ ~(-10^8 \leq x \leq 10^8)~, що описують оновлення.

Output

Виведіть ~q~ рядків, максимально можливу вартість послідовності після кожного оновлення.

1. (~21~ бал): ~1 \leq n, q \leq 200~;

2. (~30~ балів): ~1 \leq n, q \leq 3000~;

3. (~49~ балів): без додаткових обмежень.

Sample Input 1

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

Sample Output 1

2
2
0

Sample Input 2

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

Sample Output 2

2
1
3