#include<bits/stdc++.h>
using namespace std;

long long a,b,c,d,k,N,Q;
vector<long long> tab;

inline long long check(long long val){
    long long jeden = tab[val];
    val = (long long)k-(long long)val;
    long long dwa = a*(val*val*val) + b*(val*val) + c*val + d;
    if(val > N) dwa = 1e18;
    if(val == 0ll) dwa = 0ll;
    return max(dwa,jeden);
}

inline void putUI(unsigned long long n) {
    if(n==0){
        putc_unlocked(48,stdout);
        return;
    }

     char tab[20];
    long long p = 0;
    while(n != 0) {
        tab[p++] = (n % 10) + 48;
        n /= 10ll;
    }

     while(p--)
        putc_unlocked(tab[p], stdout);
}

inline void readINT(long long *n) {
   register char c = 0,
    znak_liczby = 1;
   while (c < 33) c = getc_unlocked(stdin);

   if(c==45) { znak_liczby = -1;  c = getc_unlocked(stdin); }
   (*n) = 0;

    while (c>32) {(*n)=(*n)*10 + c-48; c=getc_unlocked(stdin);}

   (*n)*=znak_liczby;
}

int main(){
    readINT(&N); readINT(&Q);
    long long x;
    for(int i = 0; i < N; i++){
        readINT(&x);
        tab.push_back(x);
    }

    tab.push_back(0);
    sort(tab.begin(),tab.end());

    for(int i = 0; i <= N/2; i++)
        tab.push_back(1e18 + i + 1);

    while(Q--){
        readINT(&a); readINT(&b); readINT(&c); readINT(&d); readINT(&k);
        int l = 0, r = k;
        while(l + 1 < r){
            int mid = (l+r)/2;
            long long x = check(mid);
            if(check(mid-2) >= x && x >= check(mid+2)){
                l = mid;
            } else {
                r = mid;
            }
        }
        long long res = check(max(0,((int)l-2)));
        for(int i = max(0,(int)l-1); i <= min((int)k,(int)l+2); i++)
            res = min(res,check(i));
        putUI(res);
        putc_unlocked('\n', stdout);
    }

}