これは問題 A「All the Trades Are the Best」の別バージョンです。このバージョンでは、各勤務期間にそれぞれ取引回数の上限があり、勤務期間はすべて 1 日の中に収まります。勤務期間がランダムに生成されることは要求されません。

あなたは投資会社のトレーダーです。ある日、あなたが取引を担当している株式の価格が、毎日まったく同じパターンを繰り返すことに気付きました。1 日は $n$ 個の等しい時間区間に分割され、第 $i$ 区間の株価は常に $a_i$ です。ある日の第 $n$ 区間が終わると、直ちに翌日の最初の区間が始まり、株価は $a_n$ から $a_1$ に変わります。これは一生に一度のチャンスです。すでに見抜いたこのパターンに従って勤務時間中に売買するだけで、確実に利益を得ることができます！

独立した $q$ 個の勤務期間が与えられます。第 $i$ 期間は時間枠 $l_i$ に始まり、時間枠 $r_i$ に終わり、両端を含みます。ここで $l_i\le r_i$ です。時間枠は時系列順に $l_i,l_i+1,\ldots,r_i$ です。

第 $i$ 勤務期間には、最大 $k_i$ 回の取引を完了できます。各取引は、株式を 1 株買い、その後の時間枠で売ることで構成され、その利益は売却価格から購入価格を引いた値です。同時に保有できる株式は最大 1 株なので、別の株式を買う前に、現在保有している株式を売らなければなりません。すべての購入と売却はその勤務期間内で行い、上記の時系列順に従う必要があります。取引をまったく行わず、利益を $0$ にすることもできます。

各勤務期間について独立に、得られる合計利益の最大値を求めてください。

入力

最初の行には、2 つの整数 $n,q$ ($1\le n\le 10^5$, $1\le q\le 10^5$) が含まれます。それぞれ、1 日の時間枠の数と勤務期間の数を表します。

2 行目には、$n$ 個の整数 $a_1,a_2,\ldots,a_n$ ($1\le a_i\le 10^6$) が含まれます。$a_i$ は、各日の第 $i$ 時間枠の株価です。

続く $q$ 行のそれぞれには、3 つの整数 $l_i,r_i,k_i$ ($1\le l_i\le r_i\le n$, $0\le k_i\le \lfloor(r_i-l_i+1)/2\rfloor$) が含まれ、第 $i$ 勤務期間とその取引回数の上限を表します。

勤務期間やその取引回数の上限について、ランダム性の保証はありません。

出力

$q$ 行を出力してください。第 $i$ 行には、最大 $k_i$ 回の取引で第 $i$ 勤務期間中に得られる利益の最大値を、1 つの整数として出力してください。

入出力例

入力 1

6 7
3 1 4 1 5 9
1 6 1
1 6 2
1 6 3
2 5 1
2 5 2
4 4 0
1 6 0

出力 1

8
11
11
4
7
0
0

注記

最初のクエリでは、時間枠 $2$ で買い、時間枠 $6$ で売ることで、$9-1=8$ の利益を得ます。

2 番目のクエリでは、時間枠 $2$ で買い、時間枠 $3$ で売り、時間枠 $4$ で再び買い、時間枠 $6$ で売ります。合計利益は $(4-1)+(9-1)=11$ です。3 番目のクエリで 3 回目の取引を許しても、利益の最大値は増えません。

6 番目と 7 番目のクエリでは、$k_i=0$ なので取引は許されず、答えは $0$ です。