#include <bits/stdc++.h> using namespace std; //#define int long long #define endl "\n" #define lc(x) (x<<1) #define rc(x) (x<<1|1) #define pii pair<int,int> #define p1(x) (x).first #define p2(x) (x).second int n,q; int a[2][100030]; long long s[100030]; int lim; inline void trs(){ memcpy(a[1],a[0],sizeof(a[1])); s[lim]=0; for(int i=lim+1;i<=2*n+1-lim;i++){ int A=max(a[1][i-1],a[1][i]); int B=max(a[1][i],a[1][i+1]); int C=max(a[1][i-1],a[1][i+1]); a[0][i]=min(min(A,B),C); s[i]=s[i-1]+(a[0][i]>=0?a[0][i]:-a[0][i]); } } inline int ask(int l,int r){ l=max(lim+1,l); r=min(2*n+1-lim,r); if(r<l)return 0; assert(l==r); return s[r]-s[l-1]; } long long ANS[50030]; int xl[50030],xr[50030],yl[50040],yr[50040]; signed main(){ // freopen("whitealbum.in","r",stdin); // freopen("whitealbum.out","w",stdout); //freopen("sample.in","r",stdin); //freopen("sample.out","w",stdout); ios::sync_with_stdio(0); cin>>n>>q; for(int i=1;i<=2*n+1;i++) cin>>a[0][i],s[i]=s[i-1]+(a[0][i]>=0?a[0][i]:-a[0][i]); int mx=0; for(int i=1;i<=q;i++) cin>>xl[i]>>xr[i]>>yl[i]>>yr[i],mx=max(xr[i],mx),yl[i]+=n+1,yr[i]+=n+1; for(int i=0;i<=n;i++){ if(i)lim++,trs(); for(int j=1;j<=q;j++) if(xl[j]<=i&&xr[j]>=i) ANS[j]+=ask(yl[j],yr[j]); } for(int i=1;i<=q;i++) cout<<ANS[i]<<endl; cout.flush(); return 0; } /* 3 3 -2 -3 2 -1 3 0 1 0 3 -3 -3 1 2 0 2 0 2 -2 2 45651 6 */