#include <fstream>

using namespace std;

ifstream f("tnia.in");
ofstream g("tnia.out");

long long int n,m,h[100001],sum[100001],a,b,c,d,i,s,q,st,dr,mid,ok,elem;

int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        f>>h[i];
        sum[i]=sum[i-1]+h[i];
    }
    f>>q;
    for(i=1;i<=q;i++)
    {
        f>>a>>b>>c>>d;
        st=a;
        dr=c;
        ok=1;
        elem=0;
        while(st<=dr&&ok==1)
        {
            mid=(st+dr)/2;
            if(h[mid]<d)
                elem=mid,st=mid+1;

            if(h[mid]>=d)
                dr=mid-1;
        }
        if(elem==0)
            s=(c-a+1)*d;
        else
            s=sum[elem]-sum[a-1]+(c-elem)*d;
        if(b>1)
        {
            st=a;
            dr=c;
            ok=1;
            elem=0;
            while(st<=dr&&ok==1)
            {
                mid=(st+dr)/2;
                if(h[mid]<b-1)
                    elem=mid,st=mid+1;

                if(h[mid]>=b-1)
                    dr=mid-1;
            }
            if(elem==0)
                s=s-(c-a+1)*(b-1);
            else
                s=s-sum[elem]+sum[a-1]-(c-elem)*(b-1);
        }
        g<<s<<"\n";
    }
    f.close();
    g.close();
    return 0;
}