#P17879. Best Trades Again

Best Trades Again

这是 All the Trades Are the Best 的另一个版本。本题中,每个工作区间都有自己的交易次数限制,所有工作区间都位于同一天内,不保证工作区间随机生成。

一天分为 nn 个等长时段,第 ii 个时段的股价为 aia_i。

给定 qq 个工作区间。第 ii 个区间从时段 lil_i 开始,在时段 rir_i 结束,包含两个端点,且 li≤ril_i\le r_i。在这个区间内,你最多可以完成 kik_i 次交易。

一次交易包含买入一股股票,然后在严格更晚的时段卖出,利润为卖出价格减去买入价格。你同一时刻最多持有一股股票,因此再次买入之前必须先卖出当前持有的股票。

所有买卖都必须在当前工作区间内发生,并符合时间顺序。你也可以不进行交易,此时利润为0。

对每个工作区间独立求出能够获得的最大总利润。

输入格式

第一行两个整数 n,qn,q,分别表示一天的时段数和工作区间数。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n,表示各时段的股价。

接下来 qq 行,每行三个整数 li,ri,kil_i,r_i,k_i,表示工作区间及其允许的最大交易次数。

数据范围:

  • 1≤n,q≤1051\le n,q\le10^5;
  • 1≤ai≤1061\le a_i\le10^6;
  • 1≤li≤ri≤n1\le l_i\le r_i\le n;
  • 0≤ki≤⌊(ri−li+1)/2⌋0\le k_i\le\lfloor(r_i-l_i+1)/2\rfloor。

工作区间和交易次数限制均无随机性保证。

输出格式

输出 qq 行,第 ii 行一个整数,表示第 ii 个工作区间内的最大总利润。

样例

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
8
11
11
4
7
0
0

样例说明

第一次询问可以在时段2买入,在时段6卖出,利润为 9−1=89-1=8。

第二次询问可以在时段2买入、时段3卖出,再在时段4买入、时段6卖出,总利润为 (4−1)+(9−1)=11(4-1)+(9-1)=11。第三次询问虽然允许多一次交易,但最大利润仍为11。

第六、七次询问的 ki=0k_i=0,不允许交易,答案为0。