Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    H, W, D = map(int, input().split())
    hw = [None for i in range(H*W+1)]

    for i in range(H):
        a = list(map(int, input().split()))
        for j in range(W):
            hw[a[j]] = [i, j]
    
    Q = int(input())

    mem = [[None for i in range(W*H + 1)] for i in range(W*H + 1)]

    for i in range(Q):
        l, r = map(int, input().split())
        if mem[l][r] != None:
            print(mem[l][r])
        else:
            ans = 0
            for t in range(l, r, D):
                ans += abs(hw[t][0] - hw[t+D][0]) + abs(hw[t][1] - hw[t+D][1])
            print(ans)
            mem[l][r]

if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline

def main():
    H, W, D = map(int, input().split())
    hw = [None for i in range(H*W+1)]

    # 各数字の座標をhw[]に格納
    for i in range(H):
        a = list(map(int, input().split()))
        for j in range(W):
            hw[a[j]] = [i, j]

    # for i in range(len(hw)):
    #     print(i, hw[i])
    
    # Dのmodごとにmod Dからの距離を計算(累積和)
    modd = [0] * (H*W + 1)
    for start in range(D):
        tmp = start + D
        cost = 0
        if tmp == D:
            tmp = D * 2
        while tmp <= (H*W):
            tmp_cost = abs(hw[tmp][0] - hw[tmp-D][0]) + abs(hw[tmp][1] - hw[tmp-D][1])
            # print("{} - {} : {}".format(tmp-D, tmp, tmp_cost))
            # print(hw[tmp-D], hw[tmp], abs(hw[tmp][0] - hw[tmp-D][0]) + abs(hw[tmp][1] - hw[tmp-D][1]))
            cost += tmp_cost
            modd[tmp] = cost
            tmp += D
    # print(modd)
    Q = int(input())
    for i in range(Q):
        l, r = map(int, input().split())
        print(modd[r] - modd[l])

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def main():
    H, W, D = map(int, input().split())
    hw = [None for i in range(H*W+1)]

    for i in range(H):
        a = list(map(int, input().split()))
        for j in range(W):
            hw[a[j]] = [i, j]
    
    Q = int(input())

    # mem = [[None for i in range(W)] for i in range(H)]

    for i in range(Q):
        l, r = map(int, input().split())
        # if mem[l][r] != None:
        #     print(mem[l][r])
        # else:
        ans = 0
        for t in range(l, r, D):
            ans += abs(hw[t][0] - hw[t+D][0]) + abs(hw[t][1] - hw[t+D][1])
        print(ans)
        # mem[l][r]

if __name__ == "__main__":
    main()

Fixed submission:
import sys
input = sys.stdin.readline

def main():
    H, W, D = map(int, input().split())
    hw = [None for i in range(H*W+1)]

    # 各数字の座標をhw[]に格納
    for i in range(H):
        a = list(map(int, input().split()))
        for j in range(W):
            hw[a[j]] = [i, j]

    # for i in range(len(hw)):
    #     print(i, hw[i])
    
    # Dのmodごとにmod Dからの距離を計算(累積和)
    modd = [0] * (H*W + 1)
    for start in range(D):
        tmp = start + D
        cost = 0
        if tmp == D:
            tmp = D * 2
        while tmp <= (H*W):
            tmp_cost = abs(hw[tmp][0] - hw[tmp-D][0]) + abs(hw[tmp][1] - hw[tmp-D][1])
            # print("{} - {} : {}".format(tmp-D, tmp, tmp_cost))
            # print(hw[tmp-D], hw[tmp], abs(hw[tmp][0] - hw[tmp-D][0]) + abs(hw[tmp][1] - hw[tmp-D][1]))
            cost += tmp_cost
            modd[tmp] = cost
            tmp += D
    # print(modd)
    Q = int(input())
    for i in range(Q):
        l, r = map(int, input().split())
        print(modd[r] - modd[l])

if __name__ == "__main__":
    main()