#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define f first
#define s second
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, q; cin >> n >> q;
vector<int> a(n);
for (int i=0; i<n; i++) {
cin >> a[i];
}
vector<vector<int>> ti(n+1, vector<int>(n));
for (int i=0; i<n; i++) {
ti[0][i] = a[i];
}
for (int t=1; t<=n; t++) {
for (int i=0; i<n; i++) {
if (i==0) {
ti[t][i] = a[i];
}
else {
ti[t][i] = max(ti[t-1][i], ti[t-1][i-1]);
}
}
}
while (q--) {
int t, l, r; cin >> t >> l >> r;
l--; r--;
ll ans=0;
for (int i=l; i<=r; i++) {
ans += ti[t][i];
}
cout << ans << "\n";
}
}
