#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')t=-1;ch=getchar(); }while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,q; namespace Subtask1 { ll a[1005][2005]; int calc(int a,int b,int c){ int mx=max(max(a,b),c); int mn=min(min(a,b),c); return a+b+c-mx-mn; } void slv(){ up(i,1,n*2+1)a[0][i]=read(); up(i,1,n)up(j,i+1,n*2+1-i)a[i][j]=calc(a[i-1][j-1],a[i-1][j],a[i-1][j+1]); up(i,0,n)up(j,i+1,n*2+1-i)a[i][j]=abs(a[i][j]); up(i,0,n)up(j,1,n*2+1)if(i)a[i][j]+=a[i-1][j]; up(i,0,n)up(j,1,n*2+1)a[i][j]+=a[i][j-1]; while(q--){ int X1=read(),X2=read(),Y1=read(),Y2=read(); Y1+=n+1;Y2+=n+1; ll res=a[X2][Y2]; if(Y1)res-=a[X2][Y1-1]; if(X1)res-=a[X1-1][Y2]; if(X1&&Y1)res+=a[X1-1][Y1-1]; printf("%lld\n",res); } } } namespace Subtask2 { const int maxn=1e5+10; ll a[105][maxn*2],s[maxn*2],ss[maxn*2]; int len; int calc(int a,int b,int c){ int mx=max(max(a,b),c); int mn=min(min(a,b),c); return a+b+c-mx-mn; } ll qry(int X,int Y){ if(X<len)return 0; if(!Y)return 0; ll res=0; if(Y>n){ int lm=2*n+1-Y;lm=min(lm,X); res=max(lm-len+1,0)*s[Y]; if(lm+1<=X){ int l=0,r=0; if(lm>=len)r=Y-1;else r=2*n+1-len; l=r-(X-max(lm+1,len)); if(l<=r)res+=ss[r]-ss[l-1]; } } else res+=s[min(n,Y)]*(X-len+1); if(X<=Y)res-=ss[X]; else res-=ss[Y]+s[Y]*(X-(Y+1)+1); return res; } void slv(){ up(i,1,n*2+1)a[0][i]=read(); len=n+1; up(i,1,n){ bool ff=1; up(j,i+1,n*2+1-i)a[i][j]=calc(a[i-1][j-1],a[i-1][j],a[i-1][j+1]),ff&=(a[i][j]==a[i-1][j]); if(ff){ len=i;break; } } up(i,0,len-1)up(j,1,n*2+1)a[i][j]=abs(a[i][j]); up(i,0,len-1)up(j,1,n*2+1)if(i)a[i][j]+=a[i-1][j]; up(i,0,len-1)up(j,1,n*2+1)a[i][j]+=a[i][j-1]; up(i,1,n*2+1)s[i]=s[i-1]+abs(a[len][i]),ss[i]=ss[i-1]+s[i]; while(q--){ int X1=read(),X2=read(),Y1=read(),Y2=read(); Y1+=n+1,Y2+=n+1; if(X2<len){ ll res=a[X2][Y2]; if(Y1)res-=a[X2][Y1-1]; if(X1)res-=a[X1-1][Y2]; if(X1&&Y1)res+=a[X1-1][Y1-1]; printf("%lld\n",res); continue; } ll res=0; if(X1<len){ res=a[len-1][Y2]; if(Y1)res-=a[len-1][Y1-1]; if(X1)res-=a[X1-1][Y2]; if(X1&&Y1)res+=a[X1-1][Y1-1]; X1=len; } res+=qry(X2,Y2)-qry(X1-1,Y2)-qry(X2,Y1-1)+qry(X1-1,Y1-1); printf("%lld\n",res); } } } void slv(){ n=read(),q=read(); if(n<=1000)Subtask1::slv(); else Subtask2::slv(); }int main(){ // freopen("whitealbum.in","r",stdin); // freopen("whitealbum.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }