#include <iostream>
#include <fstream>
#include <algorithm>
#define N 100005
using namespace std;
ifstream fin("tnia.in");
ofstream fout("tnia.out");
long long  v[N], s[N];
long long  n,m ,i,j, st, dr, mij, q, c1,l1,c2,l2, su,sl, sol;
int main()
{
    fin>>n>>m; ///n =col m=lin
    for(i=1;i<=n;i++)///col
    {
        fin>>v[i];
        s[i]=s[i-1]+v[i];///sume part
    }
    fin>>q;
    for(i=1;i<=q;i++)
    {
        fin>>c1>>l1>>c2>>l2;
        ///caut binar l2
        st=1, dr=n;
        su=0, sol=m;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(v[mij]<l2)st=mij+1;
            else sol=mij, dr=mij-1;
        }
        ///caut binar pe l1
        st=1; dr=n;
        sl=0;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(v[mij]>=l1)dr=mij-1;
            else sl=mij, st=mij+1;
        }

        if(sol<=c2 && sol>=c1)
             su=(l2-l1+1)*(c2-sol+1),sol--;
        else
        {
            if(sol<=c1)
                su=(l2-l1+1)*(c2-c1+1), sol=c1, sl=c1;
        }

        if(sol>c2) sol=c2;
        if(sl<c1)sl=c1;
        else {
            if(sl>=c2)sl=c2+1;
            else sl++;
        }
        su+=s[sol]-s[sl-1]-(l1-1)*(sol-sl+1);
        fout<<su<<"\n";
    }
    return 0;
}