Paula 喜欢做小炒。为了让菜肴尽可能美味，她需要将一个长度为 $n$ 的整数序列切分成若干段，使得这些段的总价值最大。

每一段的价值定义为该段内最大值与最小值的差。切分后序列的总价值为所有段的价值之和。

例如，如果我们把序列 $[1\ 4\ 1\ 5\ 3\ 6]$ 切分成 $[1\ 4\ 1]$ 和 $[5\ 3\ 6]$ 两段，则总价值为 $(4 - 1) + (6 - 3) = 6$。

接下来会有 $q$ 次修改，每次修改的形式为“将区间 $[l, r]$（即下标为 $l, l + 1, \dots, r$ 的元素）内的每个元素都加上 $x$”。在每次修改后，回答询问：“切分序列所能得到的最大可能总价值是多少？”。

输入格式

第一行包含两个整数 $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

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

输出样例 1

2
2
0

输入样例 2

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

输出样例 2

2
1
3

说明

样例 1 说明：

每次修改后，一种可能的最佳划分方案分别为：$[2\ 3\ 3\ 4]$；$[4\ 3]$ 和 $[3\ 4]$；以及 $[4\ 4\ 4\ 4]$。