#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
int n , q;
cin>>n>>q;
vector<int> s(2 * n + 1);
vector<int> t(q) , l(q) , r(q);
for(int i = n ;i < 2 * n ; i++)
{
cin>>s[i];
}
for(int i = 0 ; i < q ;i++)
{
cin>>t[i]>>l[i]>>r[i];
}
vector<int> arr(n + 1);
multiset<int> ms;
for(int i = n - t[0] ; i <= n ; i++)
ms.insert(s[i]);
arr[1] = *prev(ms.end());
for(int i = n+1 ; i < 2 * n ; i++)
{
ms.erase(ms.find(s[i - t[0] - 1]));
ms.insert(s[i]);
arr[i - n + 1] = *prev(ms.end());
}
for(int i = 1 ; i <= n ; i++)
{
arr[i]+=arr[i - 1];
}
for(int i = 0 ; i < q ; i++)
{
cout<<arr[r[i]] - arr[l[i] - 1]<<'\n';
}
}
