#include<bits/stdc++.h>

using namespace std;

struct tacka{
    int poz;
    int w;
};
struct tacka1{
    int poz;
    long long w;
};

struct cmp{
	bool operator() (tacka1 &p1, tacka1 &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, int u, int v, int w){
    tacka tmp;
    tmp.poz = v;
    tmp.w = w;
    g.adj[u].push_back(tmp);
}


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

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

    graf g, g1;   
    int n, m, i, q, j;
    cin >> n >> m;
    int 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){
                int v = i * m + j + 1;
                int w = a[i][j];
                addedge(g, i * m +j, v, w);
            }
            if(i < n - 1){  
                int v = i * m + j + m;
                int 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){
                int v = i * m + j - 1;
                int w = a[i][j];
                addedge(g1, i * m + j, v, w);
            }
            if(i > 0){  
                int v = i * m + j - m;
                int w = a[i][j];
                addedge(g1, i * m + j, v, w);  
            }
        }
    }
    
    dijk(g, 0);
    dijk(g1, n*m - 1);
    
    for(i = 0; i < n * m; i++) {
        g1.dis[i] += g.dis[i] + a[i / m][i - (i / m) * m];  
        g.dis[i] += g1.dis[i] + a[i / m][i - (i / m) * m];
    }
    for(i = m; i < n * m; i++) {
        g.dis[i] = min(g.dis[i], g.dis[i - m]);
    }
    for(i = n * m - 1 - m; i >= 0; i--) {
        g1.dis[i] = min(g1.dis[i], g1.dis[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(g.dis[h], g1.dis[d]) << '\n';
        }
        else{
            if(x == 0 || y == m -1)
                cout << g1.dis[d] << '\n';
            else
                cout<< g.dis[h] << '\n';
        }
    }

    return 0;
}