P9120

k=4

#include<bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int N=5e4,K=4,M=3e4;
int k;
int n;
int a[K+1][N+1];
int ans;
inline void S1(){
    int i,j;
    int mn=M,mx=0;
    for(i=1;i<=n;i++)mn=min(mn,a[1][i]),mx=max(mx,a[1][i]);
    ans=mx-mn;
    printf("%d\n",ans); 
    return ;
}
inline void S2(){
    int i,j;
    int mn1,mx1,mn2,mx2;
    mn1=mn2=M,mx1=mx2=0;
    for(i=1;i<=n;i++){
        if(a[1][i]>a[2][i])swap(a[1][i],a[2][i]);
        mn1=min(mn1,a[1][i]),mn2=min(mn2,a[2][i]);
        mx1=max(mx1,a[1][i]),mx2=max(mx2,a[2][i]); 
    }
    ans=max(mx1-mn1,mx2-mn2);
    printf("%d\n",ans);     
    return ;
}
struct ST{
    struct S{
        int h,t;
        int mx;bool cl;
        int l;
    }T[N*4+1];
    inline void F(int p,int k){T[p].mx+=k,T[p].l+=k;return ;}
    inline void PU(int p){
        if(T[p].cl)T[p<<1].mx=T[p<<1|1].mx=T[p<<1].l=T[p<<1|1].l=0,T[p<<1].cl=T[p<<1|1].cl=true,T[p].cl=false;
        F(p<<1  ,T[p].l);    
        F(p<<1|1,T[p].l);
        T[p].l=0;
        return ;
    }
    inline void PD(int p){
        T[p].mx=max(T[p<<1].mx,T[p<<1|1].mx);
        return ;
    }
    inline void B(int p,int l,int r){
        T[p].h=l,T[p].t=r;T[p].mx=T[p].l=0;T[p].cl=false;
        if(l==r)return ;
        int mid=l+r>>1;
        B(p<<1  ,l    ,mid);
        B(p<<1|1,mid+1,r  );
    }
    inline void CL(int p){T[p].mx=T[p].cl=0,T[p].cl=true;}
    inline void UD(int p,int l,int r,int k){
        if(l<=T[p].h&T[p].t<=r){F(p,k);return ;}
        int mid=T[p].h+T[p].t>>1;
        PU(p);
        if(l<=mid)UD(p<<1  ,l,r,k);
        if(r> mid)UD(p<<1|1,l,r,k);
        PD(p);
        return ; 
    }
    inline int   Q(int p,int l,int r){
        if(l<=T[p].h&T[p].t<=r)return T[p].mx;
        int ans=0;
        int mid=T[p].h+T[p].t>>1;
        PU(p);
        if(l<=mid)ans=max(ans,Q(p<<1  ,l,r));
        if(r> mid)ans=max(ans,Q(p<<1|1,l,r));
        return ans; 
    }
}st;
int mn3,mx3;
vector<int> g;
inline bool C3(int k){
    int i,j;
    int mn;
    //1,2
    st.CL(1);
    for(i=1;i<=n;i++){
        g.clear();
        if(a[1][i]<=mn3+k&&a[2][i]>=mx3-k)g.pb(a[3][i]);
        if(a[2][i]<=mn3+k&&a[3][i]>=mx3-k)g.pb(a[1][i]);
        if(a[3][i]<=mn3+k&&a[1][i]>=mx3-k)g.pb(a[2][i]);
        if(!g.size())break;
        sort(g.begin(),g.end());
        mn=mn3-1;
        for(auto t:g)st.UD(1,max(mn+1,t-k),t,1),mn=t;
    }
    if(st.Q(1,mn3,mx3)==n)return true;
    //1,3
    st.CL(1);
    for(i=1;i<=n;i++){
        g.clear();
        if(a[1][i]<=mn3+k&&a[3][i]>=mx3-k)g.pb(a[2][i]);
        if(a[2][i]<=mn3+k&&a[1][i]>=mx3-k)g.pb(a[3][i]);
        if(a[3][i]<=mn3+k&&a[2][i]>=mx3-k)g.pb(a[1][i]);
        if(!g.size())break;
        sort(g.begin(),g.end());
        mn=mn3-1;
        for(auto t:g)st.UD(1,max(mn+1,t-k),t,1),mn=t;
    }
    if(st.Q(1,mn3,mx3)==n)return true;
    return false;  
}
inline void S3(){
    int i;
    mn3=M,mx3=0;
    for(i=1;i<=n;i++){
        mn3=min(mn3,min(a[1][i],min(a[2][i],a[3][i])));
        mx3=max(mx3,max(a[1][i],max(a[2][i],a[3][i])));
    }
    int l=0,r=mx3-mn3,mid;
    st.B(1,mn3,mx3);
    while(l<r){
        mid=l+r>>1;
        if(C3(mid))r=mid;
        else       l=mid+1;
    }
    printf("%d\n",r);
    return ;
}
pii f[K+1];int tf;
struct E{
    int h;
    int l,r;
    int k;
}e[N*K+1];int tt;
inline bool C(E x,E y){
    if(x.h!=y.h)return x.h<y.h;
    if(x.k!=y.k)return x.k>y.k;
    return false;
}
int X[K*2+1],tx,Y[K*2+1],ty;
bool G[K*2+1][K*2+1]; 
inline bool C4(int k){
    int i,j,l;
    //1,2
    tt=0;
    int xh,xl,xr;
    int yh,yl,yr;
    for(i=1;i<=n;i++){
        tf=0; 
        if(a[1][i]<=mn3+k&&a[2][i]>=mx3-k)f[++tf]=mp(a[3][i],a[4][i]);
        if(a[2][i]<=mn3+k&&a[3][i]>=mx3-k)f[++tf]=mp(a[4][i],a[1][i]);
        if(a[3][i]<=mn3+k&&a[4][i]>=mx3-k)f[++tf]=mp(a[1][i],a[2][i]);
        if(a[4][i]<=mn3+k&&a[1][i]>=mx3-k)f[++tf]=mp(a[2][i],a[3][i]);
        if(!tf)break;
        sort(f+1,f+tf+1);
        for(j=1;j<=tf;j++){
            xh=max(mn3,f[j].fi-k),xl=max(mn3,f[j].se-k),xr=f[j].se;
            for(l=1 ;l<j;l++){
                yh=        f[l].fi   ,yl=max(mn3,f[l].se-k),yr=f[l].se;
                
                if(xh<=yh){
                    if(yl<=xl)xl=max(xl,yr);
                    if(yr>=xr)xr=min(xr,yl);
                }  
            }
            if(xl<=xr)e[++tt]=(E){xh,xl,xr, 1};
            xh=        f[j].fi   ,xl=max(mn3,f[j].se-k),xr=f[j].se;
            for(l=tf;l>j;l--){
                yh=max(mn3,f[l].fi-k),yl=max(mn3,f[l].se-k),yr=f[l].se;
                if(xh>=yh){
                    if(yl<=xl)xl=max(xl,yr);
                    if(yr>=xr)xr=min(xr,yl);
                }
            }
            if(xl<=xr)e[++tt]=(E){xh,xl,xr,-1};
        }
        printf("\n");
    }
    if(i>n){
        sort(e+1,e+tt+1,C);
        st.CL(1);
        for(i=1;i<=tt;i++){
            st.UD(1,e[i].l,e[i].r,e[i].k);
            if(st.Q(1,mn3,mx3)==n)return true; 
        }
    }
    //1,3
    tt=0;
    for(i=1;i<=n;i++){  
        if(a[1][i]<=mn3+k&&a[3][i]>=mx3-k)f[++tf]=mp(a[2][i],a[4][i]);
        if(a[2][i]<=mn3+k&&a[4][i]>=mx3-k)f[++tf]=mp(a[3][i],a[1][i]);
        if(a[3][i]<=mn3+k&&a[1][i]>=mx3-k)f[++tf]=mp(a[4][i],a[2][i]);
        if(a[4][i]<=mn3+k&&a[2][i]>=mx3-k)f[++tf]=mp(a[1][i],a[3][i]);
        if(!tf)break;
        sort(f+1,f+tf+1);
        for(j=1;j<=tf;j++){
            xh=max(mn3,f[j].fi-k),xl=max(mn3,f[j].se-k),xr=f[j].se;
            for(l=1 ;l<j;l++){
                yh=        f[l].fi   ,yl=max(mn3,f[l].se-k),yr=f[l].se;
                if(xh<=yh){
                    if(yl<=xl)xl=max(xl,yr);
                    if(yr>=xr)xr=min(xr,yl);
                }  
            }
            if(xl<=xr)e[++tt]=(E){xh,xl,xr, 1};
            xh=        f[j].fi   ,xl=max(mn3,f[j].se-k),xr=f[j].se;
            for(l=tf;l>j;l--){
                yh=max(mn3,f[l].fi-k),yl=max(mn3,f[l].se-k),yr=f[l].se;
                if(xh>=yh){
                    if(yl<=xl)xl=max(xl,yr);
                    if(yr>=xr)xr=min(xr,yl);
                }
            }
            if(xl<=xr)e[++tt]=(E){xh,xl,xr,-1};
        } 
    }
    if(i>n){
        sort(e+1,e+tt+1,C);
        st.CL(1);
        for(i=1;i<=tt;i++){
            st.UD(1,e[i].l,e[i].r,e[i].k);
            if(st.Q(1,mn3,mx3)==n)return true; 
        }
    }
    //1,4
    tt=0;
    for(i=1;i<=n;i++){
        tf=0;  
        if(a[1][i]<=mn3+k&&a[4][i]>=mx3-k)f[++tf]=mp(a[2][i],a[3][i]);
        if(a[2][i]<=mn3+k&&a[1][i]>=mx3-k)f[++tf]=mp(a[3][i],a[4][i]);
        if(a[3][i]<=mn3+k&&a[2][i]>=mx3-k)f[++tf]=mp(a[4][i],a[1][i]);
        if(a[4][i]<=mn3+k&&a[3][i]>=mx3-k)f[++tf]=mp(a[1][i],a[2][i]);
        if(!tf)break;
        sort(f+1,f+tf+1);
        for(j=1;j<=tf;j++){
            xh=max(mn3,f[j].fi-k),xl=max(mn3,f[j].se-k),xr=f[j].se;
            for(l=1 ;l<j;l++){
                yh=        f[l].fi   ,yl=max(mn3,f[l].se-k),yr=f[l].se;
                if(xh<=yh){
                    if(yl<=xl)xl=max(xl,yr);
                    if(yr>=xr)xr=min(xr,yl);
                }  
            }
            if(xl<=xr)e[++tt]=(E){xh,xl,xr, 1};
            xh=        f[j].fi   ,xl=max(mn3,f[j].se-k),xr=f[j].se;
            for(l=tf;l>j;l--){
                yh=max(mn3,f[l].fi-k),yl=max(mn3,f[l].se-k),yr=f[l].se;
                if(xh>=yh){
                    if(yl<=xl)xl=max(xl,yr);
                    if(yr>=xr)xr=min(xr,yl);
                }
            }
            if(xl<=xr)e[++tt]=(E){xh,xl,xr,-1};
        }
    }
    if(i>n){
        sort(e+1,e+tt+1,C);
        st.CL(1);
        for(i=1;i<=tt;i++){
            st.UD(1,e[i].l,e[i].r,e[i].k);
            if(st.Q(1,mn3,mx3)==n)return true; 
        }
    }
    return false;
} 
inline void S4(){
    int i;
    mn3=M,mx3=0;
    for(i=1;i<=n;i++){
        mn3=min(mn3,min(min(a[1][i],a[2][i]),min(a[3][i],a[4][i])));
        mx3=max(mx3,max(max(a[1][i],a[2][i]),max(a[3][i],a[4][i])));
    }
    int l=0,r=mx3-mn3,mid;
    st.B(1,mn3,mx3);
    while(l<r){
        mid=l+r>>1;
        if(C4(mid))r=mid;
        else       l=mid+1;
    }
    printf("%d\n",r);
    return ;
}
inline int R(){
    char c=getchar();
    int s=1;
    for(;!('0'<=c&&c<='9'||c=='-');c=getchar());
    if(c=='-'){
        s=-1;
        c=getchar();
    }
    int num=0;
    while('0'<=c&&c<='9'){
        num=num*10+(c-'0');
        c=getchar();
    }
    num=num*s;
    return num;
}
int main(){
    int i,j; 
  //  freopen("lock.in","r",stdin);
  //  freopen("lock.out","w",stdout);
    int T=R();k=R();
    while(T--){
        n=R();
        for(i=1;i<=k;i++)
            for(j=1;j<=n;j++)
                a[i][j]=R();
        if(k==1)S1(); 
        if(k==2)S2();
        if(k==3)S3();
        if(k==4)S4();
    } 
    return 0;
}