//============================================================================
// Name        : main2019.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <deque>
using namespace std;

class nwidx{
public:
	int num;
	int idx;
	nwidx(int n, int i): num(n), idx(i){}
};

void findMax(int N, int B, int K, int *src, int *tar){
	deque<nwidx> dq;
	for(int i = 0; i < N; i++){
		nwidx temp(src[i*K], i);
		while(!dq.empty() && dq.front().idx <= i - B){
			dq.pop_front();
		}
		while(!dq.empty() && dq.back().num <= temp.num){
			dq.pop_back();
		}
		dq.push_back(temp);
		if(i >= B-1) tar[(i-B+1)*K] = dq.front().num;
	}
}

void findMin(int N, int B, int K, int *src, int *tar){
		deque<nwidx> dq;
		for(int i = 0; i < N; i++){
			nwidx temp(src[i*K], i);
			while(!dq.empty() && dq.front().idx <= i - B){
				dq.pop_front();
			}
			while(!dq.empty() && dq.back().num >= temp.num){
				dq.pop_back();
			}
			dq.push_back(temp);
			if(i >= B-1) tar[(i-B+1)*K] = dq.front().num;
		}
}

int main() {
	int N, B, Q;
	cin >> N >> B >> Q;
	if(B == 1){
		for(int i = 0; i < Q; i++){
			cout << 0 << endl;
		}
		return 0;
	}
	int field[62501];
	int max1[62501], max2[62501];
	int min1[62501], min2[62501];
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			cin >> field[i * N + j];
		}
	}
	for(int i = 0; i < N; i++){
		findMax(N, B, 1, field+i*N, max1+i*(N-B+1));
		findMin(N, B, 1, field+i*N, min1+i*(N-B+1));
	}
	for(int i = 0; i < N-B+1; i++){
		findMax(N, B, N-B+1, max1+i, max2+i);
		findMin(N, B, N-B+1, min1+i, min2+i);
	}
	/*
	for(int i = 0; i < N*(N-B+1); i++){
		cout << max1[i] << " ";
	}
	cout << endl;
	for(int i = 0; i < N*(N-B+1); i++){
		cout << min1[i] << " ";
	}
	cout << endl;
	for(int i = 0; i < (N-B+1)*(N-B+1); i++){
		cout << max2[i] << " ";
	}
	cout << endl;
	for(int i = 0; i < (N-B+1)*(N-B+1); i++){
		cout << min2[i] << " ";
	}
	cout << endl;
	*/
	for(int i = 0; i < Q; i++){
		int x, y;
		cin >> x >> y;
		x--; y--;
		cout << max2[x*(N-B+1)+y] - min2[x*(N-B+1)+y] << endl;
	}
	//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
	return 0;
}