import sys



import numpy as np



input = sys.stdin.readline





def dfs(H, W, D, A, Q, LR, ans):

    position = [(-1, -1)] * (H * W + 1)

    for h in range(H):

        for w in range(W):

            position[A[h][w]] = (h, w)



    mp = np.zeros(shape=(H * W + 1), dtype=np.int64)



    for i in range(1, H * W + 1 - D):

        h, w = position[i]

        y, x = position[i + D]

        mp[i + D] = abs(x - w) + abs(y - h)



    for d in range(1, D + 1):

        mp[d::D] = np.cumsum(mp[d::D])



    for i in range(Q):

        l, r = LR[i]

        ans[i] = mp[r] - mp[l]





def main():

    H, W, D = list(map(int, input().split()))

    A = np.zeros(shape=(H, W), dtype=np.int64)

    for i in range(H):

        A[i] = tuple(map(int, input().split()))

    Q = int(eval(input()))

    LR = np.zeros(shape=(Q, 2), dtype=np.int64)

    for i in range(Q):

        LR[i] = tuple(map(int, input().split()))



    ans = np.zeros(shape=Q, dtype=np.int64)

    dfs(H, W, D, A, Q, LR, ans)



    print(("\n".join(map(str, ans))))





if __name__ == "__main__":

    main()

import sys

from itertools import accumulate



input = sys.stdin.readline





def dfs(H, W, D, A, Q, LR):

    position = [(-1, -1)] * (H * W + 1)

    for h in range(H):

        for w in range(W):

            position[A[h][w]] = (h, w)



    mp = [0] * (H * W + 1)



    for i in range(1, H * W + 1 - D):

        h, w = position[i]

        y, x = position[i + D]

        mp[i + D] = abs(x - w) + abs(y - h)



    for d in range(1, D + 1):

        mp[d::D] = list(accumulate(mp[d::D]))



    ans = [mp[r] - mp[l] for l, r in LR]

    return ans





def main():

    H, W, D = list(map(int, input().split()))

    A = [None] * H

    for i in range(H):

        A[i] = tuple(map(int, input().split()))

    Q = int(eval(input()))

    LR = [None] * Q

    for i in range(Q):

        LR[i] = tuple(map(int, input().split()))



    ans = [0] * Q

    ans = dfs(H, W, D, A, Q, LR)



    print(("\n".join(map(str, ans))))





if __name__ == "__main__":

    main()

import sys
import numpy as np

input = sys.stdin.readline


def dfs(H, W, D, A, Q, LR, ans):
    position = [(-1, -1)] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)
    mp = np.zeros(shape=(H * W + 1), dtype=np.int64)
    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i + D] = abs(x - w) + abs(y - h)
    for d in range(1, D + 1):
        mp[d::D] = np.cumsum(mp[d::D])
    for i in range(Q):
        l, r = LR[i]
        ans[i] = mp[r] - mp[l]


def main():
    H, W, D = list(map(int, input().split()))
    A = np.zeros(shape=(H, W), dtype=np.int64)
    for i in range(H):
        A[i] = tuple(map(int, input().split()))
    Q = int(eval(input()))
    LR = np.zeros(shape=(Q, 2), dtype=np.int64)
    for i in range(Q):
        LR[i] = tuple(map(int, input().split()))
    ans = np.zeros(shape=Q, dtype=np.int64)
    dfs(H, W, D, A, Q, LR, ans)
    print(("\n".join(map(str, ans))))


if __name__ == "__main__":
    main()

import sys
from itertools import accumulate

input = sys.stdin.readline


def dfs(H, W, D, A, Q, LR):
    position = [(-1, -1)] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)
    mp = [0] * (H * W + 1)
    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i + D] = abs(x - w) + abs(y - h)
    for d in range(1, D + 1):
        mp[d::D] = list(accumulate(mp[d::D]))
    ans = [mp[r] - mp[l] for l, r in LR]
    return ans


def main():
    H, W, D = list(map(int, input().split()))
    A = [None] * H
    for i in range(H):
        A[i] = tuple(map(int, input().split()))
    Q = int(eval(input()))
    LR = [None] * Q
    for i in range(Q):
        LR[i] = tuple(map(int, input().split()))
    ans = [0] * Q
    ans = dfs(H, W, D, A, Q, LR)
    print(("\n".join(map(str, ans))))


if __name__ == "__main__":
    main()

-import numpy as np +from itertools import accumulate -def dfs(H, W, D, A, Q, LR, ans): +def dfs(H, W, D, A, Q, LR): -    mp = np.zeros(shape=(H * W + 1), dtype=np.int64) +    mp = [0] * (H * W + 1) -        mp[d::D] = np.cumsum(mp[d::D]) -    for i in range(Q): -        l, r = LR[i] -        ans[i] = mp[r] - mp[l] +        mp[d::D] = list(accumulate(mp[d::D])) +    ans = [mp[r] - mp[l] for l, r in LR] +    return ans -    A = np.zeros(shape=(H, W), dtype=np.int64) +    A = [None] * H -    LR = np.zeros(shape=(Q, 2), dtype=np.int64) +    LR = [None] * Q -    ans = np.zeros(shape=Q, dtype=np.int64) -    dfs(H, W, D, A, Q, LR, ans) +    ans = [0] * Q +    ans = dfs(H, W, D, A, Q, LR)