#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
//#define int long long
using namespace std;

#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

namespace out{
    char buffer[1<<21];int p1=-1;const int p2 = (1<<21)-1;
    inline void flush(){fwrite(buffer,1,p1+1,stdout),p1=-1;}
    inline void putc(const char &x) {if(p1==p2)flush();buffer[++p1]=x;}
    template <typename T>void write(T x) {
        static char buf[15];static int len=-1;if(x>=0){do{buf[++len]=x%10+48,x/=10;}while (x);}else{putc('-');do {buf[++len]=-(x%10)+48,x/=10;}while(x);}
        while (len>=0)putc(buf[len]),--len;
    }
}
 
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
 
#define maxn 100005
#define inf 0x3f3f3f3f
#define ll long long
 
// 最大子段和比较支持合并
// 序列分块，每块只有 O(B*B) 个 值域的区间
// 这些区间的 node 可以预处理（空间需要逐块处理）
// 如何预处理？
// 再分治，把两个 O((B/2)*(B/2)) 的合并起来
 
int n,m,B;
int ql[maxn],qr[maxn],vl[maxn],vr[maxn],tol[maxn],tor[maxn];
int a[maxn];
int t[maxn<<1],id[maxn<<1],len;

struct node{
    ll sum,l,r,res;
    node(ll S=0,ll L=0,ll R=0,ll E=0){sum=S,l=L,r=R,res=E;}
    inline friend node operator +(node a,node b){
        return node(
            a.sum+b.sum,
            max(a.l,b.l+a.sum),max(b.r,a.r+b.sum),
            max(max(a.res,b.res),a.r+b.l));
    }
    inline friend node operator +(node a,ll b){
        return node(
            a.sum+b,
            max(a.l,a.sum+b),max(0ll,b+a.r),
            max(a.res,b+a.r));
    }
    void operator +=(node b){
    //	(*this)=(*this)+b;return;
    	l=max(l,b.l+sum);
    	res=max(max(res,b.res),r+b.l);
		r=max(r+b.sum,b.r);
    	sum+=b.sum;
    }
    void operator +=(int b){
    //	(*this)=(*this)+b;return;
    	l=max(l,sum+b);
    	r=max(0ll,b+r);
    	res=max(res,r);
    	sum+=b;
    }
};
 
node res[maxn];
int pool[maxn],*pti=pool;
node pool2[240005],*pt=pool2;
 
int *val[63];
node *f[63];
int idl[403],idr[403],siz[63];
 
void merge(int p,int l,int r)
{
    val[p]=pti,pti+=(r-l+1);
    if(l==r){
        val[p][0]=a[l];
        siz[p]=1;
        f[p]=pt,pt+=1;
        f[p][0]=node(a[l],max(a[l],0),max(a[l],0),max(a[l],0));
        return;
    }
    int mid=l+r>>1;
    merge(p+1,l,mid),merge(p+2,mid+1,r);
    int szl=siz[p+1],szr=siz[p+2];
    int pl=0,pr=0,np=0;
    while(pl<szl&&pr<szr){
        int x=val[p+1][pl],y=val[p+2][pr];
        val[p][np++]=min(x,y);
        if(x<=y)idl[pl++]=np-1;
        if(y<=x)idr[pr++]=np-1;
    }
    while(pl<szl)val[p][np++]=val[p+1][pl],idl[pl++]=np-1;
    while(pr<szr)val[p][np++]=val[p+2][pr],idr[pr++]=np-1;
    siz[p]=np;
//  cout<<"merge "<<p<<' '<<l<<' '<<r<<endl<<pl<<" "<<pr<<" "<<np<<endl;
//  For(i,0,szl-1)cout<<idl[i]<<' ';puts("  L");
//  For(i,0,szr-1)cout<<idr[i]<<" ";puts("  R"); 
//  For(i,0,np-1)cout<<val[p][i]<<" ";puts("  V");
    f[p]=pt; pt+=np*np;
    
    node *t,*t2;
	int j,j1,lim;
	
//	for(j=0,t=f[p];j<np*np;++j,++t) (*t)=node();
	For(i,0,np-1){
		lim=i*np+np;
		for(j=i*np+i;j<lim;++j)f[p][j]=node();
	}
//    For(i,0,np-1) For(j,i,np-1) f[p][i*np+j]=node();
    
    For(i,0,szl-1)
		For(i1,(i?idl[i-1]+1:0),idl[i]){
			for(j=i,t=f[p+1]+i*szl+j;j<szl;++j,++t)
				for(j1=idl[j],t2=f[p]+i1*np+j1,lim=(j==szl-1?np:idl[j+1]);j1<lim;++j1,++t2)
					(*t2)=(*t);
		}
	For(i,0,szr-1)
		For(i1,(i?idr[i-1]+1:0),idr[i]){
			for(j=i,t=f[p+2]+i*szr+j;j<szr;++j,++t)
				for(j1=idr[j],t2=f[p]+i1*np+j1,lim=(j==szr-1?np:idr[j+1]);j1<lim;++j1,++t2)
					(*t2)+=(*t);
		}
}
 
void solve(int L,int R)
{
    pti=pool;pt=pool2;
    merge(0,L,R);
     
    int p1=0,p2=1;
    while(p1<siz[0]&&p2<=len){
        if(val[0][p1]<t[p2])++p1;
        else id[p2++]=p1;
    }
    while(p2<=len)id[p2++]=p1;
     
//  S.clear();
//  For(i,L,R)S.insert(a[i]);
//  if(S.size()!=siz[0])exit(0);
     
//  For(i,0,siz[0]-1)cout<<val[0][i]<<' ';puts("");
//  For(i,1,len)cout<<id[i]<<" ";puts("");
    For(i,1,m){
        if(ql[i]>R||qr[i]<L)continue;
        int l=vl[i],r=vr[i];
        if(ql[i]>L){
            For(j,ql[i],min(R,qr[i]))
                if(a[j]>=l&&a[j]<=r) res[i]+=a[j];//cout<<"Brute "<<a[j]<<' '<<"to "<<i<<endl;
        }
        else if(qr[i]<R){
            For(j,L,qr[i])
                if(a[j]>=l&&a[j]<=r) res[i]+=a[j];//cout<<"Brute "<<a[j]<<' '<<"to "<<i<<endl;
        }
        else if(id[tol[i]]!=id[tor[i]])
    //      cout<<"tol tor "<<id[tol[i]]<<' '<<id[tor[i]]<<endl,
    //      res[i]=res[i]+f[0][id[tol[i]]][id[tor[i]]-1];
            res[i]+=f[0][id[tol[i]]*siz[0]+id[tor[i]]-1];
    }
}
 
signed main()
{
    n=read(),m=read();
    For(i,1,n)a[i]=read();
    For(i,1,m){
        int l=read(),r=read(),vl=read(),vr=read();
        ql[i]=l,qr[i]=r;
        ::vl[i]=vl,::vr[i]=vr;
        t[++len]=vl,t[++len]=vr+1;
    }
    sort(t+1,t+len+1);
    len=unique(t+1,t+len+1)-t-1;
    For(i,1,m){
        tol[i]=lower_bound(t+1,t+len+1,vl[i])-t;
        tor[i]=lower_bound(t+1,t+len+1,vr[i]+1)-t;
    }
    B=sqrt(n)*0.8;
//  B=n;
    int bcnt=(n-1)/B+1;
    For(i,1,bcnt)solve((i-1)*B+1,min(n,i*B));
    For(i,1,m)printf("%lld\n",res[i].res);
    return 0;
}
/*
6 1
-1 1 -4 5 -1 4
2 5 -1 5
 
*/