Description

You are given an array $a$ containing $n$ integers. Then there are $q$ updates. Each update gives integers $l, r, x$, meaning to add $x$ to all elements in $[l, r]$.

Define the weight of an interval as the maximum value in the interval minus the minimum value in the interval. Now you need to split array $a$ into several consecutive intervals. Define the weight of an array that has been split into several intervals as the sum of the weights of all its intervals. For each update, find the maximum possible array weight among all ways to split the array after that update.

Input Format

The first line contains integers $n, q$, representing the length of the array and the number of updates.

The second line contains $n$ integers $a_i$.

The next $q$ lines each contain integers $l, r, x$, describing an update.

Output Format

Output $q$ lines. On the $i$-th line, output the maximum possible array weight among all splits of array $a$ after the $i$-th update.

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

2
2
0

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

2
1
3

Hint

Explanation of Sample 1

Constraints and Notes

This problem uses bundled testdata.

For $100\%$ of the testdata, $1 \le n, q \le 2 \times 10^5$, $-10^8 \le a_i, x \le 10^8$, and $1 \le l \le r \le n$.

Additional Notes

The scoring follows the original COCI problem settings, with a full score of $110$.

Translated from COCI2020-2021 CONTEST #5 T5 Sjeckanje.

Translated by ChatGPT 5