Buggy python submission (verdict: Time Limit Exceeded):
import sys

def main():
    input = sys.stdin.readline
    H, W, D = map(int, input().split())
    d = {}

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

    A = [[0 for _ in range(H*W+1)] for _ in range(H*W+1)]
    for r in range(H * W, 0, -1):
        for l in range(r - D, 0, -D):
            a = d[l]
            b = d[l+D]
            A[l][r] = A[l+D][r] + abs(a[0] - b[0]) + abs(a[1] - b[1])

    Q = int(input())
    for _ in range(Q):
        L, R = map(int, input().split())
        print(A[L][R])


if __name__ == '__main__':
    main()


Fixed submission:
import sys

def main():
    input = sys.stdin.readline
    H, W, D = map(int, input().split())
    d = [0] * (H*W + 1)

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

    A = [0] * (H*W + 1)
    for l in range(H * W - D, 0, -1):
        a = d[l]
        b = d[l+D]
        A[l] = A[l+D] + abs(a[0] - b[0]) + abs(a[1] - b[1])

    Q = int(input())
    for _ in range(Q):
        L, R = map(int, input().split())
        print(A[L] - A[R])


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

def main():
    input = sys.stdin.readline
    H, W, D = map(int, input().split())
    d = {}

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

    A = [[0 for _ in range(H*W)] for _ in range(H*W)]
    for i in range(H * W):
        for j in range(i + D, H * W):
            ans = 0
            L, R = i + 1, j + 1
            if (R - L) % D != 0:
                continue
            while L != R:
                a = d[L]
                b = d[L+D]
                ans += abs(a[0] - b[0]) + abs(a[1] - b[1])
                L += D
            A[i][j] = ans

    Q = int(input())
    for _ in range(Q):
        L, R = map(int, input().split())
        print(A[L-1][R-1])


if __name__ == '__main__':
    main()


Fixed submission:
import sys

def main():
    input = sys.stdin.readline
    H, W, D = map(int, input().split())
    d = [0] * (H*W + 1)

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

    A = [0] * (H*W + 1)
    for l in range(H * W - D, 0, -1):
        a = d[l]
        b = d[l+D]
        A[l] = A[l+D] + abs(a[0] - b[0]) + abs(a[1] - b[1])

    Q = int(input())
    for _ in range(Q):
        L, R = map(int, input().split())
        print(A[L] - A[R])


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys

def main():
    input = sys.stdin.readline
    H, W, D = map(int, input().split())
    d = {}

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

    Q = int(input())
    for _ in range(Q):
        ans = 0
        L, R = map(int, input().split())
        while L != R:
            a = d[L]
            b = d[L+D]
            ans += abs(a[0] - b[0]) + abs(a[1] - b[1])
            L += D
        print(ans)


if __name__ == '__main__':
    main()

Fixed submission:
import sys

def main():
    input = sys.stdin.readline
    H, W, D = map(int, input().split())
    d = [0] * (H*W + 1)

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

    A = [0] * (H*W + 1)
    for l in range(H * W - D, 0, -1):
        a = d[l]
        b = d[l+D]
        A[l] = A[l+D] + abs(a[0] - b[0]) + abs(a[1] - b[1])

    Q = int(input())
    for _ in range(Q):
        L, R = map(int, input().split())
        print(A[L] - A[R])


if __name__ == '__main__':
    main()