#include <bits/stdc++.h>
using namespace std;
#if __has_include("all.hpp")
#include "all.hpp"
#else
#include <atcoder/all>
#endif
using namespace atcoder;
using ard=array<long long,11>;
const long long INF = 1e15; 
const ard init={0,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF};
ard op(ard a, ard b) {
    ard tmp=init;
    for(int i=0;i<11;i++){
        for(int j=0;j+i<11;j++){
            tmp[i+j]=min(tmp[i+j],a[i]+b[j]);
        }
    }
    return tmp;
}
ard e() { return init; }
int main(void){
    int n,q;
    cin>>n>>q;
    vector<ard>si(n,init);
    for(int i=0;i<n;i++){
        si[i][0]=0;
        cin>>si[i][1];
    }
    segtree<ard, op, e> seg(si);
    while(q--){
        int l,r,k;
        cin>>l>>r>>k;
        cout<<seg.prod(l-1,r)[k]<<endl;
    }
    return 0;
}