#include <fstream>
#define N 1001
#include <deque>
#include <cstring>
#include <functional>
std::ifstream fin("struti.in");
std::ofstream fout("struti.out");
int m, n, k, A[N][N], arr1[N], arr2[N], sol1[N], sol2[N], k2, val1[N][N], val2[N][N];
std::deque<int> D;
inline int M(int x, int y){
    if(x >= y)
        return true;
    return false;
}
inline int mm(int x, int y){
    if(x < y)
        return true;
    return false;
}
void findMax(int *arr, int *sol, int Dy, int n, std::function<int(int, int)> func){
    D.clear();
    std::fill_n(sol, sizeof(sol), 0);
    for(int j = 1; j <= n; j++){
        while(!D.empty() && func(arr[j], arr[D.back()]) ){
            D.pop_back();
        }
        D.push_back(j);
        if(j - Dy >= 1 && D.front() == j - Dy){
            D.pop_front();
        }
        if(j - Dy >= 0)
            sol[++k2] = arr[D.front()];
    }
}

int compute(int A[][N], int Dx, int Dy){
    int min_diff = (1 << 30);
    std::fill_n(*val1, sizeof(val1) / sizeof(**val1), 0);
    std::fill_n(*val2, sizeof(val2) / sizeof(**val2), 0);
    int col = 1, valk2;
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++)
            arr1[j] = arr2[j] = A[i][j];
        findMax(arr1, sol1, Dy, n, M); k2 = 0;
        findMax(arr2, sol2, Dy, n, mm);

        for(int j = 1; j <= k2; j++){
            val1[col][j] = sol1[j] ;
            val2[col][j] = sol2[j] ;
        }
        valk2 = k2, k2 = 0, col ++;
    }
    int cnt = 0;
    for(int jj = 1; jj <= valk2; jj++){
        for(int ii = 1; ii <= m ; ii++){
            cnt ++;
            arr1[cnt] = val1[ii][jj];
            arr2[cnt] = val2[ii][jj];
        }
        findMax(arr1, sol1, Dx, m, M);k2 = 0; cnt = 0;
        findMax(arr2, sol2, Dx, m, mm);
        k2 = 0; cnt = 0;
        for(int ii = 1; ii <= m - Dx + 1; ii++)
            min_diff = std::min(min_diff, sol1[ii] - sol2[ii]);
    }
    return min_diff;
}
int main(){
    fin >> m >> n >> k;
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++)
            fin >> A[i][j];
    }
    int Dx, Dy;
    for(int Q = 1; Q <= k; Q++){
        fin >> Dx >> Dy;
        int diffmin = (1 << 30);
        diffmin = std::min(diffmin, compute(A, Dx, Dy));
        if(Dx != Dy){
            diffmin = std::min(diffmin, compute(A, Dy, Dx));
        }
        fout << diffmin << "\n";
    }
}