#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define ff first
#define ss second

struct ruter{
    int p, c, a, b, ind;
};

struct stan{
    int i, j, dl;
};

bool cmp1(const ruter& a, const ruter& b){
    return a.p < b.p;
}

bool cmp2(const stan& a, const stan& b){
    return a.dl > b.dl;
}

const int NMAX = 2e3 + 1;
const int INF = 2e9 + 7;

int minuj[NMAX][NMAX], maxuj[NMAX][NMAX], dp[NMAX][NMAX];

void build(vi& h){
    int n = h.size() - 1;

    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            minuj[i][j] = min(minuj[i][j - 1], h[j]);
            maxuj[i][j] = max(maxuj[i][j - 1], h[j]);
        }
    }
}

const int N = 1024 * 2;
int tree[NMAX][2 * N][2];

void upd(int v, int val, int t, int p){
    v += N;
    tree[p][v][t] = min(tree[p][v][t], val);
    v >>= 1;

    while(v){
        tree[p][v][t] = min(tree[p][2 * v][t], tree[p][2 * v + 1][t]);
        v >>= 1;
    }
}

int query(int l, int r, int p, int t){
    l += N;
    r += N;
    int wyn = INF;

    while(l <= r){
        if(l & 1){
            wyn = min(wyn, tree[p][l][t]);
            l++;
        }
        if(!(r & 1)){
            wyn = min(wyn, tree[p][r][t]);
            r--;
        }
        l >>= 1;
        r >>= 1;
    }

    return wyn;
}

pii znajdz(int start, int mn, int mx, int n){
    int l = 1, r = start;

    while(l < r){
        int mid = (l + r) >> 1;
        if(minuj[mid][start] >= mn && maxuj[mid][start] <= mx)
            r = mid;
        else
            l = mid + 1;
    }

    int L = l;

    l = start;
    r = n;

    while(l < r){
        int mid = (l + r + 1) >> 1;
        if(minuj[start][mid] >= mn && maxuj[start][mid] <= mx)
            l = mid;
        else
            r = mid - 1;
    }

    return {L, l};
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    vi h(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> h[i];
        minuj[i][i] = h[i];
        maxuj[i][i] = h[i];
    }

    build(h);

    for(int z = 0; z < NMAX; z++){
        for(int i = 1; i < 2 * N; i++){
            tree[z][i][0] = INF;
            tree[z][i][1] = INF;
        }
    }

    vector<ruter> rut(k);

    for(int i = 0; i < k; i++){
        cin >> rut[i].p >> rut[i].c >> rut[i].a >> rut[i].b;
        rut[i].ind = i;
    }

    sort(rut.begin(), rut.end(), cmp1);

    vector<stan> stany;

    for(int i = 0; i < k; i++){
        for(int j = 0; j < k; j++){
            if(rut[i].a <= rut[j].a && rut[i].b <= rut[j].b){
                stany.pb({i, j, rut[j].b - rut[i].a});
            }
        }
    }

    sort(stany.begin(), stany.end(), cmp2);

    for(int i = 0; i < NMAX; i++){
        for(int j = 0; j < NMAX; j++){
            dp[i][j] = INF;
        }
    }

    for(stan st : stany){
        int i = st.i;
        int j = st.j;

        int lewy = rut[i].a;
        int prawy = rut[j].b;

        pii prz = znajdz(rut[i].p, lewy, prawy, n);

        if(prz.ff > rut[j].p || prz.ss < rut[j].p) continue;

        if(prz.ff == 1 && prz.ss == n){
            dp[i][j] = 0;
        }else{
            int l = 0, r = k;

            while(l < r){
                int mid = (l + r) >> 1;
                if(rut[mid].p >= prz.ff)
                    r = mid;
                else
                    l = mid + 1;
            }

            int L = l;

            l = 0;
            r = k;

            while(l < r){
                int mid = (l + r) >> 1;
                if(rut[mid].p <= prz.ss)
                    l = mid + 1;
                else
                    r = mid;
            }

            int R = l - 1;

            if(L <= R){
                int x = query(L, R, j, 0);
                int y = query(L, R, i, 1);

                dp[i][j] = min(dp[i][j], min(x, y));
            }
        }

        if(dp[i][j] != INF){
            upd(i, dp[i][j] + rut[i].c, 0, j);
            upd(j, dp[i][j] + rut[j].c, 1, i);

                   if(dp[i][j] != INF){
            upd(i, dp[i][j] + rut[i].c, 0, j);
            upd(j, dp[i][j] + rut[j].c, 1, i);

            if(i == j){
                for(int z = 0; z < k; z++){
                    if(rut[i].b > rut[z].b){
                        upd(i, dp[i][i] + rut[i].c, 0, z);
                    }

                    if(rut[z].a > rut[i].a){
                        upd(i, dp[i][i] + rut[i].c, 1, z);
                    }

                    if(rut[z].a <= rut[i].a && rut[z].b >= rut[i].b &&
                       (rut[z].a < rut[i].a || rut[z].b > rut[i].b) &&
                       dp[z][z] != INF &&
                       prz.ff <= rut[z].p && rut[z].p <= prz.ss){
                        dp[i][i] = min(dp[i][i], dp[z][z] + rut[z].c);
                    }
                }
            }
        }
        }
    }

    vi ans(k);

    for(int i = 0; i < k; i++){
        int ind = rut[i].ind;

        if(h[rut[i].p] < rut[i].a || h[rut[i].p] > rut[i].b){
            ans[ind] = -1;
        }else if(dp[i][i] == INF){
            ans[ind] = -1;
        }else{
            ans[ind] = dp[i][i] + rut[i].c;
        }
    }

    for(int x : ans) cout << x << "\n";

    return 0;
}