問題文

日本は 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
• 入力は全て整数

入力例 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