喜欢序列

题号：NC266843
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小蓝喜欢一种特殊的序列： $x,x+1,x+2,x+3,...$ （其中 $x$ 可以是任意整数）。

小灰灰现在获得了一个长度为 $n$ 的数组： $A_1, A_2,..., A_n$ ，他打算将这个数组拆分成连续的若干段，其中每一段都是小蓝喜欢的序列。

若小灰灰将数组拆分成了 $k$ 个连续的段，其中第 $i$ 个连续段的长度记为 $s_i$ 那么小蓝对小灰灰的崇拜度就是： $\sum_{i = 1}^{k}s_i^2$ 。

小红听说了这件事后给小灰灰上了点难度，小红将会进行 $m$ 次操作，第 $i$ 次操作会选取一个区间 $[l_i, r_i]$ 并将区间中所有数都加上 $w_i$ 。

请你帮小灰灰求出每一次操作后他在最优拆分方式下可以获得的最大崇拜度是多少。

输入描述:

第一行输入两个空格分隔的整数分别代表  和 。

接下来一行输入  个空格分隔的整数分别代表：。

接下来  行，第  行将会输入三个空格分隔的整数分别代表 ， 和 。

保证：

输出描述:

输出共  行，第  行代表在  次操作后小灰灰能获得的最大崇拜度。

示例1

输入

复制

9 4
1 2 3 5 6 7 9 10 11
1 6 0
4 4 -1
7 8 -1
4 8 1

输出

复制