rec.
code:

#include <iostream>
#include <limits>
#define int long long
#define MAXN 1005
using namespace std;
int h, w, n;
int a[MAXN][MAXN], bmin[MAXN][MAXN], cmin[MAXN][MAXN];
int bmax[MAXN][MAXN], cmax[MAXN][MAXN];
int q[MAXN], front, back;
signed main() {
    cin >> h >> w >> n;
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= h; i++) { // 计算 bmin
        front = 1; back = 0;
        for (int j = 1; j <= n; j++) {
            while (front <= back && a[i][q[back]] <= a[i][j]) {
                back--;
            }
            q[++back] = j;
        }
        bmin[i][1] = a[i][q[front]];
        for (int j = n + 1; j <= w; j++) {
            while (front <= back && q[front] <= j - n) {
                front++;
            }
            while (front <= back && a[i][q[back]] <= a[i][j]) {
                back--;
            }
            q[++back] = j;
            bmin[i][j - n + 1] = a[i][q[front]];
        }
    }
    for (int j = 1; j <= w - n + 1; j++) { // 计算 cmin
        front = 1; back = 0;
        for (int i = 1; i <= n; i++) {
            while (front <= back && bmin[q[back]][j] <= bmin[i][j]) {
                back--;
            }
            q[++back] = i;
        }
        cmin[1][j] = bmin[q[front]][j];
        for (int i = n + 1; i <= h; i++) {
            while (front <= back && q[front] <= i - n) {
                front++;
            }
            while (front <= back && bmin[q[back]][j] <= bmin[i][j]) {
                back--;
            }
            q[++back] = i;
            cmin[i - n + 1][j] = bmin[q[front]][j];
        }
    }
    
    for (int i = 1; i <= h; i++) { // 计算 bmax
        front = 1; back = 0;
        for (int j = 1; j <= n; j++) {
            while (front <= back && a[i][q[back]] >= a[i][j]) {
                back--;
            }
            q[++back] = j;
        }
        bmax[i][1] = a[i][q[front]];
        for (int j = n + 1; j <= w; j++) {
            while (front <= back && q[front] <= j - n) {
                front++;
            }
            while (front <= back && a[i][q[back]] >= a[i][j]) {
                back--;
            }
            q[++back] = j;
            bmax[i][j - n + 1] = a[i][q[front]];
        }
    }
    for (int j = 1; j <= w - n + 1; j++) { // 计算 cmax
        front = 1; back = 0;
        for (int i = 1; i <= n; i++) {
            while (front <= back && bmax[q[front]][j] >= bmax[i][j]) {
                back--;
            }
            q[++back] = i;
        }
        cmax[1][j] = bmax[q[front]][j];
        for (int i = n + 1; i <= h; i++) {
            while (front <= back && q[front] <= i - n) {
                front++;
            }
            while (front <= back && bmax[q[back]][j] >= bmax[i][j]) {
                back--;
            }
            q[++back] = i;
            cmax[i - n + 1][j] = bmax[q[front]][j];
        }
    }
    int ans = numeric_limits<int>::max();
    for (int i = 1; i <= h - n + 1; i++) {
        for (int j = 1; j <= w - n + 1; j++) {
            ans = min(ans, abs(cmin[i][j] - cmax[i][j]));
        }
    }
    cout << ans << endl;
    return 0;
}