#include<bits/stdc++.h>

using namespace std;

struct tacka{
    long long poz, w;
};

struct cmp{
	bool operator() (tacka &p1, tacka &p2){
		return p1.w>p2.w;
	}
};

struct graf{
    vector<vector<tacka> > adj;
    vector<bool> vis;
    int n;
    vector<long long> dis;
};

void init(graf &g, int n) {
    g.n = n;
    g.adj.resize(n);
    g.vis.resize(n, false);
    g.dis.resize(n, LONG_LONG_MAX);
} 

void addedge(graf &g, long long u, long long v, long long w){
    tacka tmp;
    tmp.poz = v;
    tmp.w = w;
    g.adj[u].push_back(tmp);
}


void dijk(graf &g, long long u) {
    priority_queue<tacka, vector<tacka>, cmp> pq;
    tacka tmp;
    tmp.poz = u;
    tmp.w = 0;
    pq.push(tmp);
    g.dis[tmp.poz] = 0;
    while(pq.size()) {
        tmp = pq.top();
        pq.pop();
        long long a;
        a = tmp.poz;
        if(g.vis[a] == 1) continue;
        g.vis[a] = 1;
        for(int i = 0; i < g.adj[a].size(); i++) {
            if(tmp.w + g.adj[a][i].w < g.dis[g.adj[a][i].poz]) {
                tacka t;
                t.poz = g.adj[a][i].poz;
                t.w = tmp.w + g.adj[a][i].w;
                pq.push(t);
                g.dis[g.adj[a][i].poz] = tmp.w + g.adj[a][i].w;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    graf g, g1;   
    int n, m, i, q, j;
    cin >> n >> m;
    long long a[n][m];
    for(i = 0; i < n; i++) {
        for(j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }
    init(g, n * m);
    init (g1, n * m);
    for(i = 0; i < n; i++) {
        for(j = 0; j < m; j++) {
            if(j < m - 1){
                long long v = i * m + j + 1;
                long long w = a[i][j];
                addedge(g, i * m +j, v, w);
            }
            if(i < n - 1){  
                long long v = i * m + j + m;
                long long w = a[i][j];
                addedge(g, i * m + j, v, w);  
            }
        }
    }
    for(i = n - 1; i >= 0; i--) {
        for(j = m- 1; j >= 0; j--) {
            if(j > 0){
                long long v = i * m + j - 1;
                long long w = a[i][j];
                addedge(g1, i * m + j, v, w);
            }
            if(i > 0){  
                long long v = i * m + j - m;
                long long w = a[i][j];
                addedge(g1, i * m + j, v, w);  
            }
        }
    }
    
    dijk(g, 0);
    dijk(g1, n*m - 1);
    vector<long long> v;
    v.resize( n * m);
    for(i = 0; i < n * m; i++) {
        v[i] = g.dis[i] + g1.dis[i] + a[i / m][i - (i / m) * m];
    }
    vector<long long> gore;
    vector<long long> dole;
    gore.resize(n * m);
    dole.resize(n * m);
    for(i = 0; i < n * m; i++) {
        gore[i] = v[i];
        dole[i] = v[i];
    }
    for(i = m; i < n * m; i++) {
        gore[i] = min(v[i], gore[i - m]);
    }
    for(i = n * m - 1 - m; i >= 0; i--) {
        dole[i] = min(v[i], dole[i + m]);
    }

    cin >> q;
    for(i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        int h, d;
        h = (x - 1) * m + y + 1;
        d = (x + 1) * m + y - 1;
        if(x != 0 && y != m - 1 && x != n - 1 && y != 0) {
            cout << min(gore[h], dole[d]) << '\n';
        }
        else{
            if(x == 0 || y == m -1)
                cout << dole[d] << '\n';
            else
                cout<<gore[h] << '\n';
        }
    }


    return 0;
}