#include <stdio.h>

 #include <string.h>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 int val[][];

 int mm[];

 int dpmin[][][][];//最小值

 int dpmax[][][][];//最大值

 void initRMQ(int n,int m)

 {

     for(int i = ;i <= n;i++)

         for(int j = ;j <= m;j++)

             dpmin[i][j][][] = dpmax[i][j][][] = val[i][j];

     for(int ii = ; ii <= mm[n]; ii++)

         for(int jj = ; jj <= mm[m]; jj++)

             if(ii+jj)

                 for(int i = ; i + (<<ii) -  <= n; i++)

                     for(int j = ; j + (<<jj) -  <= m; j++)

                     {

                         if(ii)

                         {

                             dpmin[i][j][ii][jj] = min(dpmin[i][j][ii-][jj],dpmin[i+(<<(ii-))][j][ii-][jj]);

                             dpmax[i][j][ii][jj] = max(dpmax[i][j][ii-][jj],dpmax[i+(<<(ii-))][j][ii-][jj]);

                         }

                         else

                         {

                             dpmin[i][j][ii][jj] = min(dpmin[i][j][ii][jj-],dpmin[i][j+(<<(jj-))][ii][jj-]);

                             dpmax[i][j][ii][jj] = max(dpmax[i][j][ii][jj-],dpmax[i][j+(<<(jj-))][ii][jj-]);

                         }

                     }

 }

 //查询矩形的最大值

 int rmq1(int x1,int y1,int x2,int y2)

 {

     int k1 = mm[x2-x1+];

     int k2 = mm[y2-y1+];

     x2 = x2 - (<<k1) + ;

     y2 = y2 - (<<k2) + ;

     return max(max(dpmax[x1][y1][k1][k2],dpmax[x1][y2][k1][k2]),max(dpmax[x2][y1][k1][k2],dpmax[x2][y2][k1][k2]));

 }

 //查询矩形的最小值

 int rmq2(int x1,int y1,int x2,int y2)

 {

     int k1 = mm[x2-x1+];

     int k2 = mm[y2-y1+];

     x2 = x2 - (<<k1) + ;

     y2 = y2 - (<<k2) + ;

     return min(min(dpmin[x1][y1][k1][k2],dpmin[x1][y2][k1][k2]),min(dpmin[x2][y1][k1][k2],dpmin[x2][y2][k1][k2]));

 }

 int main()

 {

     mm[] = -;

     for(int i = ;i <= ;i++)

         mm[i] = ((i&(i-))==)?mm[i-]+:mm[i-];

     int N,B,K;

     while(scanf("%d%d%d",&N,&B,&K)==)

     {

         for(int i = ;i <= N;i++)

             for(int j = ;j <= N;j++)

                 scanf("%d",&val[i][j]);

         initRMQ(N,N);

         int x,y;

         while(K--)

         {

             scanf("%d%d",&x,&y);

             printf("%d\n",rmq1(x,y,x+B-,y+B-)-rmq2(x,y,x+B-,y+B-));

         }

     }

     return ;

 }