Description

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, \ldots , r$”. After each update, answer the query “What is the maximum possible value of the chopped sequence?”.

Input

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

The second line contains $n$ integers $a_i$ $(−10^8 \le a_i \le 10^8)$, the sequence Paula needs to chop.

Each of the following $q$ lines contains integers $l, r$ $(1 \le l \le r \le n)$, and $x$ $(−10^8 \le x \le 10^8)$, describing an update.

Output

Output $q$ lines, the maximum possible value of the sequence after each update.

Example 1

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

2
2
0

Possible optimal choppings after each update are respectively: $[2,3,3,4]$,$[4,3] [3,4]$, and $[4,4,4,4]$.

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

2
1
3

Scoring