#include <bits/stdc++.h>
using namespace std;
#ifndef lisie_bimbi
#define endl '\n'
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,bmi2,fma")
#endif
using ll = long long;
const ll inf = 1'000'000'000'000'000'000;
const int N = 200'010;
#define int long long
struct query{
int l;
int r;
int ind;
};
void solve(){
int n, q;
cin >> n >> q;
vector<ll> a(n);
for(int i = 0; i < n; i++){
cin >> a[i];
}
vector<vector<query>> qq(n + 1);
for(int i = 0; i < q; i++){
int l, r, t;
cin >> t >> l >> r;
l--;
qq[t].push_back({l, r, i});
}
vector<ll> ans(q);
for(int i = 0; i <= n; i++){
for(auto [l, r, ind] : qq[i]){
int aa = 0;
for(int i = l; i < r; i++){
aa += a[i];
}
ans[ind] = aa;
}
for(int i = n - 1; i > 0; i--){
a[i] = max(a[i], a[i - 1]);
}
}
for(auto i : ans){
cout << i << endl;
}
cout << endl;
}
signed main(){
#ifdef lisie_bimbi
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
#endif
cin.tie(nullptr)->sync_with_stdio(false);
int t = 1;
//cin >> t;
while(t--){
solve();
}
}
