#include <stdio.h>
#include <vector>

using namespace std;

vector < int > unapred[1000000];
vector < int > a[1000000];
vector < int > unazad[1000000];
vector < int > vrednosti[1000000];
vector < int > redmax[1000000];
vector < int > kolmax[1000000];
vector < int > res[1000000];


int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
        {
            int x;
            scanf("%d",&x);
            unapred[i].push_back(x);
            unazad[i].push_back(x);
            vrednosti[i].push_back(0);
            redmax[i].push_back(-1);
            kolmax[i].push_back(-1);
            a[i].push_back(x);
            res[i].push_back(-1);
        }
    //unapred
    for (int i=1;i<n;i++) unapred[i][0]+=unapred[i-1][0];
    for (int i=1;i<m;i++) unapred[0][i]+=unapred[0][i-1];
    for (int i=1;i<n;i++)
        for (int j=1;j<m;j++)
        {
            unapred[i][j]+=min(unapred[i-1][j],unapred[i][j-1]);
        }
    /*for (int i=0;i<n;i++,printf("\n"))
        for (int j=0;j<m;j++) printf("%d ",unapred[i][j]);*/

    //unazad
    for (int i=n-2;i>=0;i--) unazad[i][m-1]+=unazad[i+1][m-1];
    for (int i=m-2;i>=0;i--) unazad[n-1][i]+=unazad[n-1][i+1];
    for (int i=n-2;i>=0;i--)
        for (int j=m-2;j>=0;j--) unazad[i][j]+=min(unazad[i+1][j],unazad[i][j+1]);
    /*printf("\n");
    for (int i=0;i<n;i++,printf("\n"))
        for (int j=0;j<m;j++) printf("%d ",unazad[i][j]);*/

    //vrednosti
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++) vrednosti[i][j]=unapred[i][j]+unazad[i][j]-a[i][j];
    /*printf("\n");
    for (int i=0;i<n;i++,printf("\n"))
        for (int j=0;j<m;j++) printf("%d ",vrednosti[i][j]);*/


    //redmax
    for (int i=0;i<n-1;i++)
    {
        redmax[i][m-1]=vrednosti[i][m-1];
        for (int j=m-2;j>=0;j--) redmax[i][j]=min(vrednosti[i][j],redmax[i][j+1]);
    }
    /*printf("\n");
    for (int i=0;i<n;i++,printf("\n"))
        for (int j=0;j<m;j++) printf("%d ",redmax[i][j]);*/


    //kolmax
    for (int j=0;j<m-1;j++)
    {
        kolmax[n-1][j]=vrednosti[n-1][j];
        for (int i=n-2;i>=0;i--) kolmax[i][j]=min(vrednosti[i][j],kolmax[i+1][j]);
    }
    /*printf("\n");
    for (int i=0;i<n;i++,printf("\n"))
        for (int j=0;j<m;j++) printf("%d ",kolmax[i][j]);*/



    //res
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
        {
            if (i==0) res[i][j]=kolmax[i+1][j-1];
            else if (j==0) res[i][j]=redmax[i-1][j+1];
            else if (i==n-1) res[i][j]=redmax[i-1][j+1];
            else if (j==m-1) res[i][j]=kolmax[i+1][j-1];
            else res[i][j]=min(kolmax[i+1][j-1],redmax[i-1][j+1]);
        }
    /*printf("\n");
    for (int i=0;i<n;i++,printf("\n"))
        for (int j=0;j<m;j++) printf("%d ",res[i][j]);*/

    int q;
    scanf("%d",&q);
    while (q)
    {
        q--;
        int x,y;
        scanf("%d%d",&x,&y);
        x--;y--;
        printf("%d\n",res[x][y]);
    }

    return 0;
}