/*洛谷 U4792 Acheing 二维线段树 n*n*logn*logn T成傻逼2333 */#include<iostream>#include<cstdio>#include<cstring>#define maxn 1010#define lc k*2#define rc k*2+1#define mid (l+r)/2using namespace std;int n,m,k,g[maxn][maxn],x,y,z;int x1,x2,y1,y2,ans=0x7fffffff;int mx[maxn*4][maxn*4],mxx[maxn*4][maxn*4];void Insert_y(int kx,int k,int l,int r){    mx[kx][k]=min(mx[kx][k],z);    mxx[kx][k]=max(mxx[kx][k],z);    if(l==r)return;    if(y<=mid)Insert_y(kx,lc,l,mid);    else Insert_y(kx,rc,mid+1,r);    mx[kx][k]=min(mx[kx][lc],mx[kx][rc]);    mxx[kx][k]=max(mxx[kx][lc],mxx[kx][rc]);}void Insert_x(int k,int l,int r){    Insert_y(k,1,1,m);    if(l==r)return;    if(x<=mid)Insert_x(lc,l,mid);    else Insert_x(rc,mid+1,r);}int Query_miny(int kx,int k,int l,int r){    if(y1<=l&&y2>=r)return mx[kx][k];    if(y2<=mid)return Query_miny(kx,lc,l,mid);    else if(y1>mid)return Query_miny(kx,rc,mid+1,r);    else return min(Query_miny(kx,lc,l,mid),Query_miny(kx,rc,mid+1,r));}int Query_maxy(int kx,int k,int l,int r){    if(y1<=l&&y2>=r)return mxx[kx][k];    if(y2<=mid)return Query_maxy(kx,lc,l,mid);    else if(y1>mid)return Query_maxy(kx,rc,mid+1,r);    else return max(Query_maxy(kx,lc,l,mid),Query_maxy(kx,rc,mid+1,r));}int Query_minx(int k,int l,int r){    if(x1<=l&&x2>=r)return Query_miny(k,1,1,m);    if(x2<=mid)return Query_minx(lc,l,mid);    else if(x1>mid)return Query_minx(rc,mid+1,r);    else return min(Query_minx(lc,l,mid),Query_minx(rc,mid+1,r));}int Query_maxx(int k,int l,int r){    if(x1<=l&&x2>=r)return Query_maxy(k,1,1,m);    if(x2<=mid)return Query_maxx(lc,l,mid);    else if(x1>mid)return Query_maxx(rc,mid+1,r);    else return max(Query_maxx(lc,l,mid),Query_maxx(rc,mid+1,r));}int main(){    scanf("%d%d%d",&n,&m,&k);    memset(mxx,-127/3,sizeof(mxx));    memset(mx,127/3,sizeof(mx));    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++){        scanf("%d",&g[i][j]);        x=i;y=j;z=g[i][j];        Insert_x(1,1,n);    }    for(int i=k;i<=n;i++)        for(int j=k;j<=m;j++){            x1=i-k+1;x2=i;y1=j-k+1;y2=j;            int minner=Query_minx(1,1,n);            int maxxer=Query_maxx(1,1,n);            ans=min(ans,maxxer-minner);        }    printf("%d\n",ans);    return 0;}

/*洛谷 U4792 Acheing 单调队列运用 解决二维线段树超时的问题 */#include<cstdio>#include<cstring>#define maxn 1010using namespace std;int n,m,k,g[maxn][maxn],mx[maxn][maxn],mi[maxn][maxn],mxx[maxn][maxn],mxi[maxn][maxn];int q[maxn],head,tail,ans=0x7fffffff;int init(){    int x=0,f=1;char s=getchar();    while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();}    while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();}    return x*f;}int min(int x,int y){    return x<y?x:y;}void Ready(){    for(int j=1;j<=m;j++){        head=1;tail=0;        for(int i=1;i<=n;i++){            int x=g[i][j];            while(head<=tail&&x>g[q[tail]][j])tail--;            q[++tail]=i;            if(i-q[head]>=k)head++;            mx[i][j]=g[q[head]][j];        }    }    for(int j=1;j<=m;j++){        head=1;tail=0;        for(int i=1;i<=n;i++){            int x=g[i][j];            while(head<=tail&&x<g[q[tail]][j])tail--;            q[++tail]=i;            if(i-q[head]>=k)head++;            mi[i][j]=g[q[head]][j];        }    }}void Solve(){    for(int i=k;i<=n;i++){        head=1;tail=0;        for(int j=1;j<=m;j++){            int x=mx[i][j];            while(head<=tail&&x>mx[i][q[tail]])tail--;            q[++tail]=j;            if(j-q[head]>=k)head++;            mxx[i][j]=mx[i][q[head]];        }    }    for(int i=k;i<=n;i++){        head=1;tail=0;        for(int j=1;j<=m;j++){            int x=mi[i][j];            while(head<=tail&&x<mi[i][q[tail]])tail--;            q[++tail]=j;            if(j-q[head]>=k)head++;            mxi[i][j]=mi[i][q[head]];        }    }}int main(){    n=init();m=init();k=init();    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)            g[i][j]=init();    Ready();Solve();    for(int i=k;i<=n;i++)        for(int j=k;j<=m;j++)            ans=min(ans,mxx[i][j]-mxi[i][j]);    printf("%d\n",ans);    return 0;}