Problem description

Algosia, jak każde dziecko w Bitocji, ma swój ulubiony ciąg N liczb a₁, a₂, …, a_N. Algosia lubi dzielić swój ciąg na spójne kawałki. Dla każdego kawałka określa jego fajność przez różnicę między największym a najmniejszym elementem danego kawałka. Przykładowo, gdyby ciąg [2 6 4 8 3 4] podzielić na kawałki [2 6 4] oraz [8 3 4], to fajność tych kawałków wyniosłaby odpowiednio 6 − 2 = 4 oraz 8 − 3 = 5. Fajnością podziału ciągu określimy przez sumę fajności każdego z jego kawałków.

Algosia zastanawia się, jak mogłaby podzielić ciąg, żeby zmaksymalizować jego fajność. Ponadto, dokona Q zmian ciągu. Każda zmiana polega na dodaniu wartości x do wszystkich elementów a_l, a_l + 1, …, a_r dla pewnych l ≤ r. Napisz program, który po każdej zmianie ciągu odpowie jaka jest maksymalna fajność pewnego podziału tego ciągu.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N oraz Q, oznaczające odpowiednio długość ciągu oraz liczbę zmian ciągu. W następnym wierszu znajduje się ciąg N liczb, oznaczające początkowe wartości ciągu. W następnych Q wierszach następują opisy kolejnych modyfikacji ciągu. Każda modyfikacja opisana jest przez trzy liczby całkowite l, r, x, oznaczające, że Algosia doda wartość x do wszystkich elementów od l-tego do r-tego włącznie.

Wyjście

Należy wypisać Q wierszy, każdy z nich opisujący największą możliwość fajność podziału ciągu po każdej modyfikacji.

Ograniczenia

1 ≤ N, Q ≤ 200 000, |a_i|, |x| ≤ 10⁸, 1 ≤ l ≤ r ≤ N.

Przykład

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

4
7
7