#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=505,M=3e5+5;
int n,Q,u[N],v[N],w[N][N],dp[N][N][2][2],c1,c2,ans[M];
struct qr{int l1,r1,l2,r2,i;}q[M],q1[M],q2[M];
void ckmax(int&a,int b){if(a<b)a=b;}
int mxl(int i,int j){return *max_element(dp[i][j][0],dp[i][j][0]+4);}
int mxr(int i,int j){return *max_element(dp[i][j][0],dp[i][j][0]+4);}
void getdpl(int l1,int r1,int l2,int r2)
{
    for(int i=r1;i>=l1;--i)for(int j=r2;j>=l2;--j)
        ckmax(dp[i][j][1][0],dp[i][j][0][0]-u[i]),
        ckmax(dp[i][j][0][1],dp[i][j][0][0]-v[j]),
        ckmax(dp[i][j][1][1],dp[i][j][1][0]-v[j]+w[i][j]),
        ckmax(dp[i][j][1][1],dp[i][j][0][1]-u[i]+w[i][j]),
        ckmax(dp[i-1][j][0][0],max(dp[i][j][0][0],dp[i][j][1][0])),
        ckmax(dp[i-1][j][0][1],max(dp[i][j][0][1],dp[i][j][1][1])),
        ckmax(dp[i][j-1][0][0],max(dp[i][j][0][0],dp[i][j][0][1])),
        ckmax(dp[i][j-1][1][0],max(dp[i][j][1][0],dp[i][j][1][1]));
}
void getdpr(int l1,int r1,int l2,int r2)
{
    for(int i=l1;i<=r1;++i)for(int j=l2;j<=r2;++j)
        ckmax(dp[i][j][1][0],dp[i][j][0][0]-u[i]),
        ckmax(dp[i][j][0][1],dp[i][j][0][0]-v[j]),
        ckmax(dp[i][j][1][1],dp[i][j][1][0]-v[j]+w[i][j]),
        ckmax(dp[i][j][1][1],dp[i][j][0][1]-u[i]+w[i][j]),
        ckmax(dp[i+1][j][0][0],max(dp[i][j][0][0],dp[i][j][1][0])),
        ckmax(dp[i+1][j][0][1],max(dp[i][j][0][1],dp[i][j][1][1])),
        ckmax(dp[i][j+1][0][0],max(dp[i][j][0][0],dp[i][j][0][1])),
        ckmax(dp[i][j+1][1][0],max(dp[i][j][1][0],dp[i][j][1][1]));
}
void solve2(int,int,int,int,int,int);
void solve1(int l1,int r1,int l2,int r2,int ql,int qr)
{
    if(l1>r1||l2>r2||ql>qr)return;
    // fprintf(stderr,"solve1 %d %d %d %d\n",l1,r1,l2,r2);
    int mid=l1+r1>>1;
    c1=c2=0;
    for(int i=ql;i<=qr;++i)
        if(q[i].l1<=mid&&q[i].r1>mid)q1[++c1]=q[i];
        else q2[++c2]=q[i];
    if(c1)
    {
        for(int pos=l2;pos<=r2;++pos)
        {
            for(int i=l1;i<=r1;++i)for(int j=l2;j<=r2;++j)memset(dp[i][j],-0x3f,sizeof(dp[i][j]));
            dp[mid][pos][0][1]=-v[pos];
            dp[mid+1][pos][0][1]=0;
            getdpl(l1,mid,l2,pos);
            getdpr(mid+1,r1,pos,r2);
            for(int i=1;i<=c1;++i)
                if(q1[i].l2<=pos&&q1[i].r2>=pos)
                    ckmax(ans[q1[i].i],mxl(q1[i].l1,q1[i].l2)+mxr(q1[i].r1,q1[i].r2));
        }
        for(int i=l1;i<=r1;++i)for(int j=l2;j<=r2;++j)memset(dp[i][j],-0x3f,sizeof(dp[i][j]));
        dp[mid+1][l2][0][0]=0;
        getdpr(mid+1,r1,l2,r2);
        for(int i=1;i<=c1;++i)
            ckmax(ans[q1[i].i],mxl(q1[i].r1,q1[i].r2));
    }
    qr=ql-1;
    for(int i=1;i<=c2;++i)
        if(q2[i].r1<=mid)q[++qr]=q2[i];
    int tmp=qr;
    for(int i=1;i<=c2;++i)
        if(q2[i].l1>mid)q[++qr]=q2[i];
    // cerr<<l2<<' '<<r2<<'\n';
    solve2(l1,mid,l2,r2,ql,tmp);
    solve2(mid+1,r1,l2,r2,tmp+1,qr);
}
void solve2(int l1,int r1,int l2,int r2,int ql,int qr)
{
    if(l1>r1||l2>r2||ql>qr)return;
    // fprintf(stderr,"solve2 %d %d %d %d\n",l1,r1,l2,r2);
    if(l2==r2)
    {
        assert(l1==r1);
        for(int i=ql;i<=qr;++i)ans[q[i].i]=max(0,w[l1][l2]-u[l1]-v[l2]);
        return;
    }
    int mid=l2+r2>>1;
    c1=c2=0;
    for(int i=ql;i<=qr;++i)
        if(q[i].l2<=mid&&q[i].r2>mid)q1[++c1]=q[i];
        else q2[++c2]=q[i];
    if(c1)
    {
        for(int pos=l1;pos<=r1;++pos)
        {
            for(int i=l1;i<=r1;++i)for(int j=l2;j<=r2;++j)memset(dp[i][j],-0x3f,sizeof(dp[i][j]));
            dp[pos][mid][1][0]=-u[pos];
            dp[pos][mid+1][1][0]=0;
            getdpl(l1,pos,l2,mid);
            getdpr(pos,r1,mid+1,r2);
            for(int i=1;i<=c1;++i)
                if(q1[i].l1<=pos&&q1[i].r1>=pos)
                    ckmax(ans[q1[i].i],mxl(q1[i].l1,q1[i].l2)+mxr(q1[i].r1,q1[i].r2));
            // cerr<<dp[1][2][0][0]<<' '<<dp[1][2][0][1]<<' '<<dp[1][2][1][0]<<' '<<dp[1][2][1][1]<<'\n';
            // cerr<<pos<<' '<<mxl(1,2)<<' '<<mxl(1,3)<<'\n';
        }
        for(int i=l1;i<=r1;++i)for(int j=l2;j<=r2;++j)memset(dp[i][j],-0x3f,sizeof(dp[i][j]));
        dp[l1][mid+1][0][0]=0;
        getdpr(l1,r1,mid+1,r2);
        for(int i=1;i<=c1;++i)
            ckmax(ans[q1[i].i],mxl(q1[i].r1,q1[i].r2));
    }
    qr=ql-1;
    for(int i=1;i<=c2;++i)
        if(q2[i].r2<=mid)q[++qr]=q2[i];
    int tmp=qr;
    for(int i=1;i<=c2;++i)
        if(q2[i].l2>mid)q[++qr]=q2[i];
    solve1(l1,r1,l2,mid,ql,tmp);
    solve1(l1,r1,mid+1,r2,tmp+1,qr);
}
int main()
{
    scanf("%d%d",&n,&Q);
    // for(int i=1;i<=n;++i)scanf("%d",u+i);
    // for(int i=1;i<=n;++i)scanf("%d",v+i);
    // for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)scanf("%d",w[i]+j);
    for(int i=1;i<=Q;++i)
        scanf("%d%d%d%d",&q[i].l1,&q[i].r1,&q[i].l2,&q[i].r2),q[i].i=i;
    solve1(1,n,1,n,1,Q);
    for(int i=1;i<=Q;++i)printf("%d\n",ans[i]);
}