Language: C++

#include <bits/stdc++.h>
using namespace std;

int table[90001][90001];//x,y

const long long int INF = 1000000000;

map<int,pair<int,int>> m; //x,y

long long int memo[90001][90001];

inline int my_abs(int input){
    if(input < 0){
        input = -input;
    }
    return input;
}

int main() {

    int h,w,d;

    cin >> h >> w >> d;

    for(int i=0; i<h; i++){
        for(int j=0; j<w; j++){
            cin >> table[j][i];
            m[table[j][i]] = make_pair(i,j);
        }
    }

    for(int i=0; i<90001; i++){
        for(int j=0; j<90001; j++){
            memo[i][j] = INF;
        }
    }

    for(int i=0; i<90001; i++){
        memo[i][i] = 0;
    }

    /*
    for(int i=h*w; i>d; i-=d){
        pair<int,int> pos = m[i];
        int tmp = my_abs(pos.first - m[i-d].first) + my_abs(pos.second - m[i-d].second);
        memo[i-d][i] = tmp;
    }*/
    /*
    for(int i=0; i<d; i++){
        for(int j=i; j<h*w-d; j+=d){
            pair<int,int> pos = m[j];
            int tmp = my_abs(pos.first - m[i+d].first) + my_abs(pos.second - m[i+d].second);
            memo[i][i+d] = tmp;
        }
    }*/

    /*
    for(int i=0; i<9; i++){
        for(int j=0; j<9; j++){
            cout << memo[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
    */

    for(int i=1; i<=h*w; i++){
        /*if(memo[i][max_r] != INF){
            continue;
        }*/
        for(int j=i; j<=h*d; j+=d){
            pair<int,int> pos = m[j];
            int tmp = my_abs(pos.first - m[j+d].first) + my_abs(pos.second - m[j+d].second);
            memo[j][j+d] = tmp;
        }
    }

    for(int i=0; i<d; i++){

        int max_r = h*w - i;

        for(int j=max_r-d; j>=0; j-=d){
            memo[j][max_r] = memo[j][j+d] + memo[j+d][max_r];
        }
    }

    int q;

    cin >> q;

    while(q--){
        int l,r;

        cin >> l >> r;

        cout << memo[l][r] << endl;
    }

    return 0;
}

Compiler output:
/tmp/ccbAsqmS.o: in function `main':
a.cc:(.text+0xda): relocation truncated to fit: R_X86_64_PC32 against symbol `m' defined in .bss section in /tmp/ccbAsqmS.o
a.cc:(.text+0x158): relocation truncated to fit: R_X86_64_PC32 against symbol `memo' defined in .bss section in /tmp/ccbAsqmS.o
a.cc:(.text+0x196): relocation truncated to fit: R_X86_64_PC32 against symbol `memo' defined in .bss section in /tmp/ccbAsqmS.o
a.cc:(.text+0x1d0): relocation truncated to fit: R_X86_64_PC32 against symbol `m' defined in .bss section in /tmp/ccbAsqmS.o
a.cc:(.text+0x1fb): relocation truncated to fit: R_X86_64_PC32 against symbol `m' defined in .bss section in /tmp/ccbAsqmS.o
a.cc:(.text+0x22f): relocation truncated to fit: R_X86_64_PC32 against symbol `m' defined in .bss section in /tmp/ccbAsqmS.o
a.cc:(.text+0x27a): relocation truncated to fit: R_X86_64_PC32 against symbol `memo' defined in .bss section in /tmp/ccbAsqmS.o
a.cc:(.text+0x307): relocation truncated to fit: R_X86_64_PC32 against symbol `memo' defined in .bss section in /tmp/ccbAsqmS.o
a.cc:(.text+0x334): relocation truncated to fit: R_X86_64_PC32 against symbol `memo' defined in .bss section in /tmp/ccbAsqmS.o
a.cc:(.text+0x360): relocation truncated to fit: R_X86_64_PC32 against symbol `memo' defined in .bss section in /tmp/ccbAsqmS.o
a.cc:(.text+0x3e8): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status