//2023年8月7日19:02:17
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a,b,n,ans=0x7f7f7f7f7f7f7f;
struct Skadi{
    int x,y,w;
}v[1005][1005];
deque<Skadi> s1,s2,zc1[1005],zc2[1005];
inline void WORK(){
    for(int j=n+1;j<=b;j++){
        for(int i=1;i<=n;i++){
            Skadi zc=v[i][j];
            while(!s1.empty()&&s1.front().w>=zc.w)s1.pop_front();
            s1.push_front(zc);
            while(!s2.empty()&&s2.front().w<=zc.w)s2.pop_front();
            s2.push_front(zc);
        }
        while(s1.back().y<=j-n)s1.pop_back();
        while(s2.back().y<=j-n)s2.pop_back();
        zc1[j]=s1;zc2[j]=s2;
        ans=min(ans,s2.back().w-s1.back().w);
    }
    for(int i=n+1;i<=a;i++){
        for(int k=n;k<=b;k++){
        for(int j=k-n+1;j<=k;j++){
            Skadi zc=v[i][j];
            while(!zc1[k].empty()&&zc1[k].front().w>=zc.w)zc1[k].pop_front();
            zc1[k].push_front(zc);
            while(!zc2[k].empty()&&zc2[k].front().w<=zc.w)zc2[k].pop_front();
            zc2[k].push_front(zc);
           
        }
         while(zc1[k].back().x<=i-n||zc1[k].back().y<=k-n)zc1[k].pop_back();
            while(zc2[k].back().x<=i-n||zc2[k].back().y<=k-n)zc2[k].pop_back();
            ans=min(ans,zc2[k].back().w-zc1[k].back().w);
        }
    }
}
signed main(){
    scanf("%d%d%d",&a,&b,&n);
    for(int i=1;i<=a;i++)
        for(int j=1;j<=b;j++)
            scanf("%d",&v[i][j].w),v[i][j].x=i,v[i][j].y=j;
    for(int j=1;j<=n;j++)
        for(int i=1;i<=n;i++){
            Skadi zc=v[i][j];
            while(!s1.empty()&&s1.front().w>=zc.w)s1.pop_front();
            s1.push_front(zc);
            while(!s2.empty()&&s2.front().w<=zc.w)s2.pop_front();
            s2.push_front(zc);
        }
    zc1[n]=s1;zc2[n]=s2;
    WORK();
    cout<<ans;
    return 0;
}

问题出在有的点没有满足条件入队，但又需要这个点，不知道怎么写 思路是一行一行地遍历，有的点遍历多次