#include <bits/stdc++.h> using namespace std; const int maxn=2e5+10; int n,q; int a[maxn]; int calc(int x,int y,int z) { if(x>y) swap(x,y); if(y>z) swap(y,z); if(x>y) swap(x,y); return y; } struct sol1 { int b[2010][2010],sum[2010][2010]; void sol() { for(int i=1;i<=2*n+1;i++) b[1][i]=a[i]; for(int i=2;i<=n+1;i++) for(int j=i+1-1;j<=2*n+1-(i-1);j++) b[i][j]=calc(b[i-1][j-1],b[i-1][j],b[i-1][j+1]); for(int i=1;i<=n+1;i++) for(int j=1;j<=2*n+1;j++) sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+abs(b[i][j]); int x1,y1,x2,y2; while(q--) { cin>>x1>>x2>>y1>>y2; x1++,x2++; y1+=n+1,y2+=n+1; cout<<sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]<<endl; } } }t1; int main() { // freopen("whitealbum.in","r",stdin); // freopen("whitealbum.out","w",stdout); ios::sync_with_stdio(false); cin>>n>>q; for(int i=1;i<=2*n+1;i++) cin>>a[i]; if(n<=1000) { t1.sol(); return 0; } return 0; } /* */