3044: 爱读书的zgt

$wx$和$zgt$应$hyd$的邀请，来到$hyd$家做客。$hyd$家里面有一间超级大的书房，书房里面一共有$n$个书柜，第$i$个书柜有$a_{i}$本书。喜欢读书的$zgt$非常高兴，但是$wx$和$hyd$早已经商量好了，只要$zgt$可以解决$wx$和$hyd$提出的难题，$zgt$就可以在$hyd$的书房里为所欲为。

$wx$给出了一个函数$f(l,r) = max(ai\ |\ l<=i<=r)$，代表第$l$个书柜到第$r$个书柜中，拥有书最多的书柜有多少本书。然后对$zgt$进行$q$次询问，每次都给出单独的$l_{j}$和$r_{j}$，要求$zgt$ 给出对应的$f(l_{j},r_{j})$的值。

$zgt$很快的就解决掉了这个问题，于是$hyd$加深了难度：$hyd$也给出了一个函数$g(x,l,r) = \sum_{y=l}^{r}f(x,y)$，也对$zgt$进行$q$次询问，即每次给出单独的$x_{j},l_{j}$ 和$r_{j}$，求$g(x_{j},l_{j},r_{j})$的值。

$zgt$这次陷入了困境，想要求助于你，请你帮$zgt$解决这个问题。

输入第一行为一个整数$T(T \leq 30)$，表示一共有$T$组测试数据。

对于每组测试数据：
第一行有两个整数$n(1 \leq n \leq 10^5)$,$q(1 \leq m \leq 10^5)$，分别表示书柜的数量和询问数。

第二行有$n$个整数，其中第$i$个整数$a_{i}(1 \leq a_{i} \leq 10^9)$，表示第$i$个书柜中书的数量。

接下来$q$行，每行有三个整数$x_{j}(1 \leq x_{j} \leq l_{j})$,$l_{j}(x_{j} \leq l_{j} \leq r_{j})$,$r_{j}(l_{j} \leq r_{j} \leq n)$，定义如题意。

对于每组测试数据一行输出$q$个整数，第$j$个数表示第$j$次询问的答案。

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

15 11 21
5 2 12