問題
長さ$ \ N \ $の数列$ \ A = (A_1,A_2,\ldots,A_N) \ $が与えられる。
- $i=1,2,\ldots,M \ $について$ \ \displaystyle \sum_{k=L_i}^{R_i} |A_k - T_i| \ $を求めよ。
入力
入力は以下の形式で標準入力から与えられる。
$N \ M$ $A_1 \ A_2 \ \ldots \ A_N$ $L_1 \ R_1 \ T_1$ $L_2 \ R_2 \ T_2$ $\vdots$ $L_M \ R_M \ T_M$
出力
出力は$ \ M \ $行からなる。$i \ $行目には$ \ i \ $番目の答えを出力せよ。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq N,M \leq 2 \times 10^5$
- $1 \leq A_i,T_i \leq 10^9$
- $1 \leq L_i \leq R_i \leq N$
- 入力は全て整数
入出力例
入力例
5 3 2 3 4 1 5 1 3 2 2 2 3 1 5 8
出力例
3 0 25