学步园

#include<iostream>//AC:t=1 w=0 WA:t=0 w=0
#include<cstdio>
using namespace std;
inline long long read(){    
    long long x=0,f=1;char ch=getchar();    
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}    
    return x*f;    
}  
long long n,m,k,ans=100000000000001LL,a[2001][2001],lmax[2001][2001],lmin[2001][2001],fmax[2001][2001],fmin[2001][2001],t,w;
pair<long long,int> q[2001];
long long Min(long long a,long long b){
	if(a<b)return a;
	else return b;
} 
int main(){
	n=read();m=read();k=read();
	if(k==0){printf("0");return 0;}
	if(k>max(n,m))k=max(n,m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			a[i][j]=read();
	for(int j=1;j<=m;j++){
		t=1;w=0;
		for(int i=1;i<=n;i++){
			while(t<=w&&a[i][j]>q[w].first)w--;
			q[++w]=make_pair(a[i][j],i);
			while(i-q[t].second>=k)t++;
			if(i>=k)lmax[i][j]=q[t].first;
		}
		t=1;w=0;
		for(int i=1;i<=n;i++){
			while(t<=w&&a[i][j]<q[w].first)w--;
			q[++w]=make_pair(a[i][j],i);
			while(i-q[t].second>=k)t++;
			if(i>=k)lmin[i][j]=q[t].first;
		}
	}
	for(int i=k;i<=n;i++){
		t=1;w=0;
		for(int j=1;j<=m;j++){
			while(t<=w&&lmax[i][j]>q[w].first)w--;
			q[++w]=make_pair(lmax[i][j],j);
			while(j-q[t].second>=k)t++;
			if(j>=k)fmax[i][j]=q[t].first;
		}
		t=1;w=0;
		for(int j=1;j<=m;j++){
			while(t<=w&&lmin[i][j]<q[w].first)w--;
			q[++w]=make_pair(lmin[i][j],j);
			while(j-q[t].second>=k)t++;
			if(j>=k)fmin[i][j]=q[t].first;
		}
	}
	for(int i=k;i<=n;i++)
		for(int j=k;j<=m;j++)
			ans=Min(ans,fmax[i][j]-fmin[i][j]);
	printf("%lld",ans);
	return 0;
}