abc089 <前缀和>

// https://atcoder.jp/contests/abc089/tasks/abc089_d
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
int h, w, d;

struct Node
{
    int l, x, y;
    Node(int l, int x, int y):l(l), x(x), y(y){}
    bool operator<(const Node &t) const
    {
        return l < t.l;
    }
};

void solv()
{
    cin >> h >> w >> d;
    vector<Node> a;
    for (int i = 1; i <= h; i ++)
        for (int j = 1; j <= w; j ++)
        {
            int t; cin >> t;
            a.push_back({t, i, j});
        }
    sort(a.begin(), a.end());
    vector<int> tot(a.size(), 0);  // 前缀和数组
    for (int i = 0; i < a.size(); i ++)
    {
        if (!tot[i])  // 每次进入, 计算出一组前缀和
        {
            int p = i;
            while (true)
            {
                int q = p + 1;
                while (q < a.size() && a[q].l < a[p].l + d) q ++;
                if (q == a.size()) break;
                tot[q] = tot[p] + abs(a[p].x - a[q].x) + abs(a[p].y - a[q].y);
                p = q;
            }
        }
    }
    int q; cin >> q;
    while (q --)
    {
        int l, r;
        cin >> l >> r;
        int p = lower_bound(a.begin(), a.end(), Node(l, 0, 0)) - a.begin();  // 注意, 这里传入Node(l, 0, 0), 直接传入{l, 0, 0}会报错
        int q = lower_bound(a.begin(), a.end(), Node(r, 0, 0)) - a.begin();
        int ans =  tot[q] - tot[p];
        cout << ans << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
	// cin >> T;
    while (T --)
    {
        solv();
    }
    return 0;
}