配点: 3 点
問題文
日本被划分为 N 个区块,从西向东第 i 个区块(以下称为区块 i )的海拔为 A_i 。
从现在开始 Q 次地壳变化将会发生。i 在第几次地壳变化中,区块 L_i, L_i+1, \cdots, R_i 的海拔会变化 V_i 。(当V_i \geq 0 时海拔上升 |V_i| ,V_i < 0 时海拔上升 |V_i| 时下降)
那么,区块 1 减去 N 时的不便定义如下。
区画 i 的海拔高度 表示为 E_i 的情况下,不便之处是 |E_1 - E_2| + |E_2 - E_3| + \cdots + |E_{N-1} - E_N|
各地壳变动后的不便请分别求出。
制約
- 1 \leq N, Q \leq 10^{5}
- -10^{9} \leq A_i, V_i \leq 10^{9}
- 1 \leq L_i \leq R_i \leq N
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N Q A_1 A_2 \cdots A_N L_1 R_1 V_1 L_2 R_2 V_2 \vdots L_Q R_Q V_Q
出力
Q 行。
列出
i 行中,i 请输出第几次地壳变动结束后的不便之处。
入力例 1
3 3 1 2 3 2 3 1 1 2 -1 1 3 2
出力例 1
3 4 4
1 次地壳变动后的各区块海拔,从西向东分别为 1, 3, 4 ,不便之处是有 |1 - 3| + |3 - 4| = 3 。
2 次地壳变动后的各区块海拔,从西向东分别为 0, 2, 4 ,不便之处是有 |0 - 2| + |2 - 4| = 4 。
3 次地壳变动后的各区块海拔,从西向东分别为 2, 4, 6 ,不便之处是有 |2 - 4| + |4 - 6| = 4 。
入力例 2
20 10 61 51 92 -100 -89 -65 -89 -64 -74 7 87 -2 51 -39 -50 63 -23 36 74 37 2 2 -45 6 19 82 2 9 36 7 13 71 16 20 90 18 20 -24 14 17 -78 10 11 -55 7 19 -26 20 20 -7
出力例 2
1164 1328 1256 1350 1440 1416 1572 1482 1430 1437