#include <stdio.h>
#include <stdbool.h>
#define INFINITY -1

//If you're reading this, hi! :)
//Nicreven#8252. love youuu <3


//So many globals!


unsigned xBad, yBad;
unsigned badProduct; //uniqueProduct explained in the Dijkstra function.
unsigned a, b; //matrix sizes
int visitedCount = 0; //Number of nodes we've visited. If this number reaches a*b, we know that we've visted every node.
int aXb; //a*b
int size = 0; //of priority queue. basically the amount of unvisited nodes.
void swap(); //2 elements of the queue
void heapify(); //heapify queue
void insert(); //insert element into queue
void deleteRoot(); //delete root of heap
int Dijkstra(); //dijkstra's algorithm
int main()
{
   scanf("%u%u", &a,&b);
   aXb = a*b; //called once for MAXIMUM SPEEED
   unsigned inputMatrix[a][b];
   unsigned weightMatrix[a][b];
   _Bool visited[a][b];
   int heap[aXb]; //Heap. Size of a*b.

   for(int i = 0; i < a; i++)
   {
       for(int j = 0; j < b; j++)
       {
            scanf("%u", &inputMatrix[i][j]);
            weightMatrix[i][j] = INFINITY;
            visited[i][j] = false;
       }
   }
   visited[0][0] = true;
   weightMatrix[0][0] = inputMatrix[0][0]; //starting node. We always go through it.
   //if this wasn't the case, we'd either set it to INFINITY or 0. The former breaks the code. The latter is incorrect.
   //Don't forget to call the function.
   unsigned badQueries;
   scanf("%u", &badQueries);
   unsigned Queries[badQueries]; //Storing bad queries so that we can loop through each one at the end
   for(int i = 0; i < badQueries; i++)
   {
       scanf("%u%u", &xBad, &yBad);
       xBad--;
       yBad--;
       Queries[i] = xBad*b+yBad;
   }
   for(int i = 0; i < badQueries; i++)
   {
       badProduct = Queries[i];
       printf("%u", Dijkstra(heap, weightMatrix, inputMatrix, visited));
       for(int j = 0; j < a; j++)
       {
            for(int k = 0; k < b; k++)
            {
                weightMatrix[j][k] = INFINITY;
                visited[j][k] = false;
            }
       }
       visited[0][0] = true;
       weightMatrix[0][0] = inputMatrix[0][0];
       visitedCount = 0;
       printf("\n");
   }
   return 0;
//       results[i] = Dijkstra(heap, weightMatrix, inputMatrix, visited);
//       printf("\n%u,%u", results[0],results[1]);
//       //Reinitialisation.
//       for(int j = 0; j < a; j++)
//       {
//            for(int k = 0; k < b; k++)
//            {
//                weightMatrix[j][k] = INFINITY;
//                visited[j][k] = false;
//            }
//       }
//       visited[0][0] = true;
//       weightMatrix[0][0] = inputMatrix[0][0];
//       visitedCount = 0;
//   }
//   for(int i = 0; i < badQueries; i++)
//   {
//       printf("\n%u", results[i]);
//   }
//   return 0;
}
int Dijkstra(int* heap, unsigned weightMatrix[a][b], unsigned inputMatrix[a][b], _Bool visited[a][b])
{
    //Every element of a matrix has a unique number assigned to it.
    //Matrices are just arrays.
    //Finding that value is just a matter of [with our variable names]
    // uniqueProduct = x*b+y
    int nodes[a][b];
    int x = 0, y = 0; //Indexes of our vertex

    while(visitedCount != aXb)
    {
        //each unvisited neighbour. max of four. We just check if it actually has that many.
          //These checks make sure we don't go out of bounds. Used to have a for loop.
          //What's the use of a for loop if we know EXACTLY what our guys are?
          //It's a lot quicker this way, to write and to read, since these conditions are
          //constant and predetermined

           if(!visited[x+1][y] && x+1<a && ((x+1)*b+y != badProduct))
           {//If we're not on the upper bound
               unsigned temp = weightMatrix[x][y]+inputMatrix[x+1][y];
               if(weightMatrix[x+1][y] > temp) //and our current weight for that guy is greater than our newly calculated weight:
               {
                   //it gets a new weight.
                   weightMatrix[x+1][y] = temp;
                   insert(heap,temp);
                   nodes[x+1][y] = temp;
               }
           }
           if(!visited[x-1][y] && x>0 && ((x-1)*b+y != badProduct))
           {//If we're not on the lower bound
               unsigned temp = weightMatrix[x][y]+inputMatrix[x-1][y];
               if(weightMatrix[x-1][y] > temp) //and our current weight for that guy is greater than our newly calculated weight:
               {
                   //it gets a new weight.
                   weightMatrix[x-1][y] = temp;
                   insert(heap,temp);
                   nodes[x-1][y] = temp;
               }

           }
           //
           if(!visited[x][y+1] && (y+1<b) && (x*b+y+1 != badProduct))
           {//If we're not on the upper bound
               unsigned temp = weightMatrix[x][y]+inputMatrix[x][y+1];
               if(weightMatrix[x][y+1] > temp) //and our current weight for that guy is greater than our newly calculated weight:
               {
                   //it gets a new weight.
                   weightMatrix[x][y+1] = temp;
                   insert(heap,temp);
                   nodes[x][y+1] = temp;
               }

           }
           if(!visited[x][y-1] && y>0 && (x*b+y-1 != badProduct))
           {//If we're not on the lower bound
               unsigned temp = weightMatrix[x][y]+inputMatrix[x][y-1];
               if(weightMatrix[x][y-1] > temp) //and our current weight for that guy is greater than our newly calculated weight:
               {
                   //it gets a new weight.
                   weightMatrix[x][y-1] = temp;
                   insert(heap,temp);
                   nodes[x][y-1] = temp;
               }
           }
        visited[x][y] = true;
        visitedCount++;
        for(int i = 0; i < a; i++)
        {
            for(int j = 0; j < b; j++)
            {
                if(nodes[i][j] == heap[0] && !visited[i][j] && i*b+j!=badProduct)
                {
                    x = i;
                    y = j;
                    break;
                }
            }
        }
        deleteRoot(heap);
    }
    return weightMatrix[x][y];
    //pseudocode and notes
    /*
    if(i<0) => don't calculate i-1; same goes for j
    otherwise:
    if weight([i+1][j]||[i][j+1] || the same but -) > weight[i][j] + input[i][j]
    => weight(-||-) = weight[i][j]+input[i][j]
    Then:
    visited[i][j] = true;
    - in main? -
    dijkstra(priorityQueue[0])
    */
    /*
    At the end of all of that, we'll have the weight for
    (N,M). Which is what we're looking for.
    We can also just include a check for the bad one.
    */
    /*
    To repeat:
    Start at node 0, 0.
    Check every node it's connected(adjacent) to (0,1), (1,0)
    Calculate their weights
    Add them to the priority queue.(Min Heap)
    Mark (0, 0) as visited && remove it from the queue.
    Heapify. <- intrinsic to the function
    Go to node Queue[0].
    Check every node it's connected(adjacent) to.
    Calculate their weights ((X+X1)(Y) or (X)(Y+Y1))
    Add them to the priority queue.
    Mark (x, y) as visited && remove it from the queue.
    Heapify. <- intrinsic to the function
    Go to node Queue[0].
    Repeat until no nodes are left.
    */
}
void swap(unsigned *a, unsigned *b)
{
  unsigned temp = *b;
  *b = *a;
  *a = temp;
}
void heapify(unsigned array[], unsigned size, unsigned i)
{
  if (size == 1)
  {
    printf("Single element in the heap");
  }
  else
  {
    unsigned smallest = i;
    unsigned l = 2 * i + 1;
    unsigned r = 2 * i + 2;
    if (l < size && array[l] < array[smallest])
      smallest = l;
    if (r < size && array[r] < array[smallest])
      smallest = r;
    if (smallest != i)
    {
      swap(&array[i], &array[smallest]);
      heapify(array, size, smallest);
    }
  }
}
void insert(unsigned array[], unsigned newNum)
{
  if (size == 0)
  {
    array[0] = newNum;
    size += 1;
  }
  else
  {
    array[size] = newNum;
    size += 1;
    for (int i = size / 2 - 1; i >= 0; i--)
    {
      heapify(array, size, i);
    }
  }
}
void deleteRoot(unsigned array[])
{
  int i = 0;

  swap(&array[i], &array[size - 1]);
  size -= 1;
  for (int i = size / 2 - 1; i >= 0; i--)
  {
    heapify(array, size, i);
  }
}