#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=1005;

int a[N][N];
int qmax[N],qmin[N];
int xmin[N][N],ymin[N][N],xmax[N][N],ymax[N][N];
int n,m,k;

signed main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		int l=1,r=1;
		qmax[1]=1;
		for(int j=2;j<=m;j++){
			while(a[i][j]>=a[i][qmax[r]]&&l<=r)r--;
			r++;qmax[r]=i;
			while(i-qmax[l]>=k)l++;
			if(j>=k)xmax[i][j-k+1]=a[i][qmax[l]];
		}
	}
	for(int i=1;i<=n;i++){
		int l=1,r=1;
		qmin[1]=1;
		for(int j=2;j<=m;j++){
			while(a[i][j]<=a[i][qmin[r]]&&l<=r)r--;
			r++;qmin[r]=i;
			while(i-qmin[l]>=k)l++;
			if(j>=k)xmin[i][j-k+1]=a[i][qmin[l]];
		}
	}
	for(int j=1;j<=m-k+1;j++){
		int l=1,r=1;
		qmax[1]=1;
		for(int i=2;i<=n;i++){
			while(xmax[i][j]>=xmax[qmax[r]][j]&&l<=r)r--;
			r++;qmax[r]=i;
			while(i-qmax[l]>=k)l++;
			if(i>=k)ymax[i-k+1][j]=xmax[qmax[l]][j];
		}
	}
	for(int j=1;j<=m-k+1;j++){
		int l=1,r=1;
		qmin[1]=1;
		for(int i=2;i<=n;i++){
			while(xmin[i][j]<=xmin[qmin[r]][j]&&l<=r)r--;
			r++;qmin[r]=i;
			while(i-qmin[l]>=k)l++;
			if(i>=k)ymin[i-k+1][j]=xmin[qmin[l]][j];
		}
	}
	int ans=0x3f3f3f3f;
	for(int i=1;i<=n-k+1;i++){
		for(int j=1;j<=m-k+1;j++){
			ans=min(ans,ymax[i][j]-ymin[i][j]);
		}
	}
	cout<<ans;
	return 0;
}

20分单调队列求助