这是 A 题 All the Trades Are the Best 的另一个版本。在本版本中，每个工作时段都有自己的交易次数上限，并且完全位于同一天内。工作时段不要求随机生成。

你是一家投资公司的交易员。某一天，你发现自己负责交易的股票每天都遵循完全相同的规律：一天被划分为 $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$ 次交易。每次交易包括买入一股股票，并在之后的某个时间段卖出，利润等于卖出价格减去买入价格。你同时最多只能持有一股股票，因此必须先卖出当前持有的股票，才能再次买入。所有买入和卖出都必须发生在该工作时段内，并遵循上述时间顺序。你也可以不进行任何交易，获得 $0$ 的利润。

对于每个工作时段，独立求出你能获得的最大总利润。

输入格式

第一行包含两个整数 $n,q$（$1\le n\le 10^5$，$1\le q\le 10^5$），分别表示一天内的时间段数量和工作时段数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le 10^6$），其中 $a_i$ 表示每天第 $i$ 个时间段内的股票价格。

接下来 $q$ 行，每行包含三个整数 $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$ 行应包含一个整数：在第 $i$ 个工作时段内最多进行 $k_i$ 次交易时，你能获得的最大利润。

样例

输入格式 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$ 买入，在时间段 $3$ 卖出，在时间段 $4$ 再次买入，在时间段 $6$ 卖出。总利润为 $(4-1)+(9-1)=11$。第三个询问允许进行第三次交易，但这不会增加最大利润。

在第六个和第七个询问中，$k_i=0$，因此不允许进行任何交易，答案为 $0$。