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, \dots, r~". After each update, answer the query "What is the maximum possible value of the chopped sequence?".

Input Specification

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 Specification

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

Constraints

Subtask	Points	Constraints
1	15	~1 \le n, q \le 200~
2	40	~1 \le n, q \le 3\,000~
3	55	No additional constraints.

Sample Input 1

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

Sample Output 1

2
2
0

Explanation for Sample Output 1

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

Sample Input 2

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

Sample Output 2

2
1
3