Sjeckanje

문제

Paula likes to prepare stir fry. In order to make it as yummy as possible, she needs to chop a sequence of n integers into segments of the maximum total value.

The value of a segment is the difference of its maximum and minimum. The value of a chopped sequence is the sum of the values of the segments.

For example if we chop the sequence [1 4 1 5 3 6] into segments [1 4 1] and [5 3 6], the total value is (4 − 1) + (6 − 3) = 6.

There will be q updates of the form “add x to the elements on indices l, l + 1, . . . , r”. After each update, answer the query “What is the maximum possible value of the chopped sequence?”.

입력

The first line contains integers n and q (1 ≤ n, q ≤ 200 000), the length of the sequence and the number of updates.

The second line contains n integers a_i (−10⁸ ≤ a_i ≤ 10⁸), the sequence Paula needs to chop. Each of the following q lines contains integers l, r (1 ≤ l ≤ r ≤ n), and x (−10⁸ ≤ x ≤ 10⁸), describing an update.

출력

Output q lines, the maximum possible value of the sequence after each 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