#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; return s[r]-s[l-1]; } long long ANS[50030]; int xl[50030],xr[50030],yl[50040],yr[50040]; int w[200300]; inline bool chk(int x,int y,int lim){ int l=y,r=y; while(l>1&&(w[l-1]>=lim)!=(w[l]>=lim))l--; while(r<2*n+1&&(w[r+1]>=lim)!=(w[r]>=lim))r++; if(x>y-l||x>r-y){ if(y-l>r-y)return w[r]>=lim; else return w[l]>=lim; } return w[l>=lim]^((x+y-l)&1); } 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; if(n*n+q*q<=2e6){ 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; } else{ // cout<<"???"; // cout.flush(); for(int i=1;i<=2*n+1;i++)cin>>w[i],w[i]+=n; while(q--){ int x,y; cin>>x,cin>>x; cin>>y,cin>>y; int l=0,r=2*n; while(l<=r){ int mid=l+r>>1; if(chk(x,y,mid))r=mid; else l=mid+1; } cout<<abs(l-n)<<endl; } } cout.flush(); return 0; } /* 6 */