Sjeckanje

Στην Paula αρέσει να μαγειρεύει stir fry. Για να το κάνει όσο πιο νόστιμο γίνεται, πρέπει να κόψει μια ακολουθία n ακεραίων σε τμήματα με τη μέγιστη συνολική τιμή.

Η τιμή ενός τμήματος είναι η διαφορά του μεγίστου και του ελαχίστου του. Η τιμή μιας κομμένης ακολουθίας είναι το άθροισμα των τιμών όλων των τμημάτων.

Για παράδειγμα, αν κόψουμε την ακολουθία ~[1\;4\;1\;5\;3\;6]~ στα τμήματα ~[1\;4\;1]~ και ~[5\;3\;6]~, η συνολική τιμή είναι ~(4 - 1) + (6 - 3) = 6~.

Θα υπάρξουν ~q~ ενημερώσεις της φόρμας "πρόσθεσε το ~x~ στα στοιχεία με δείκτες ~l, l+1,\;\ldots\;, r~". Μετά από κάθε ενημέρωση, απαντήστε στο ερώτημα "Ποια είναι η μέγιστη δυνατή τιμή της κομμένης ακολουθίας;".

Είσοδος

Η πρώτη γραμμή περιέχει ακέραιους αριθμούς ~n~ και ~q\;(1 \le n, q \le 200\,000)~, το μήκος της ακολουθίας και τον αριθμό των ενημερώσεων.

Η δεύτερη γραμμή περιέχει ~n~ ακέραιους ~a_i\;(-10^8 \le a_i \le 10^8)~, την ακολουθία που πρέπει να κόψει η Paula.

Κάθε μία από τις ακόλουθες ~q~ γραμμές περιέχει τους ακέραιους αριθμούς ~l,\;r\;(1 \le l \le r \le n)~ και ~x\;(-10^8 \le x \le 10^8)~, που περιγράφουν μια ενημέρωση.

Έξοδος

Περιλαμβάνει ~q~ γραμμές, με τη μέγιστη δυνατή τιμή της ακολουθίας μετά από κάθε ενημέρωση.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	15	~1 \le n, q \le 200~
2	40	~1 \le n, q \le 3000~
3	55	Κανένας επιπλέον περιορισμός.

Παραδείγματα

input

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

output

2
2
0

Εξήγηση του 1ου παραδείγματος:

Πιθανές βέλτιστες κοπές της ακολουθίας, μετά από κάθε ενημέρωση, είναι αντίστοιχα οι κοπές: ~[2\;3\;3\;4],\;[4\;3]\;[3\;4]~ και ~[4\;4\;4\;4]~.

input

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

output

2
1
3