Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input = sys.stdin.buffer.readline
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]
    S = [0] * (H*W + 1)

    dic = [(-1, -1) for i in range(H*W + 1)]
    for h in range(H):
        for w in range(W):
            dic[A[h][w]] = (h+1, w+1)

    for d in range(1, D+1):
        for idx in range(d, H*W+1):
            if H*W < idx+D:
                break
            i, j = dic[idx]
            x, y = dic[idx + D]
            S[idx+D] = abs(x - i) + abs(y - j) + S[idx]

    Q = int(input())
    for query in range(Q):
        le, ri = (int(i) for i in input().split())
        print(S[ri] - S[le])


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]
    num_to_xy = {}
    d_sum = [[] for _ in range(D)]
    for h in range(H):
        for w in range(W):
            num_to_xy[A[h][w]] = (h+1, w+1)
            d_sum[A[h][w] % D].append((A[h][w]))
    for d in range(D):
        d_sum[d].sort()
        cur = []
        y, x = -1, -1
        j, i = -1, -1
        for i, a in enumerate(d_sum[d]):
            if i == 0:
                y, x = num_to_xy[a]
                continue
            j, i = num_to_xy[a]
            cur.append(abs(x - i) + abs(y - j))
            y, x = j, i
        s = [0] * (len(cur) + 1)
        for i in range(0, len(cur)):
            s[i+1] = s[i] + cur[i]
        d_sum[d] = s
    Q = int(input())
    for q in range(Q):
        le, ri = (int(i) for i in input().split())
        if le % D != 0:
            print(d_sum[le % D][(ri - le % D)//D] -
                  d_sum[le % D][(le - le % D)//D])
        else:
            print(d_sum[le % D][(ri - le % D)//D-1] -
                  d_sum[le % D][(le - le % D)//D-1])


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input = sys.stdin.buffer.readline
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]
    S = [0] * (H*W + 1)

    dic = {i: (-1, -1) for i in range(1, H*W + 1)}
    for h in range(H):
        for w in range(W):
            dic[A[h][w]] = (h+1, w+1)

    for d in range(1, D+1):
        for idx in range(d, H*W+1):
            if H*W < idx+D:
                break
            i, j = dic[idx]
            x, y = dic[idx + D]
            S[idx+D] = abs(x - i) + abs(y - j) + S[idx]

    Q = int(input())
    for query in range(Q):
        le, ri = (int(i) for i in input().split())
        print(S[ri] - S[le])


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]
    num_to_xy = {}
    d_sum = [[] for _ in range(D)]
    for h in range(H):
        for w in range(W):
            num_to_xy[A[h][w]] = (h+1, w+1)
            d_sum[A[h][w] % D].append((A[h][w]))
    for d in range(D):
        d_sum[d].sort()
        cur = []
        y, x = -1, -1
        j, i = -1, -1
        for i, a in enumerate(d_sum[d]):
            if i == 0:
                y, x = num_to_xy[a]
                continue
            j, i = num_to_xy[a]
            cur.append(abs(x - i) + abs(y - j))
            y, x = j, i
        s = [0] * (len(cur) + 1)
        for i in range(0, len(cur)):
            s[i+1] = s[i] + cur[i]
        d_sum[d] = s
    Q = int(input())
    for q in range(Q):
        le, ri = (int(i) for i in input().split())
        if le % D != 0:
            print(d_sum[le % D][(ri - le % D)//D] -
                  d_sum[le % D][(le - le % D)//D])
        else:
            print(d_sum[le % D][(ri - le % D)//D-1] -
                  d_sum[le % D][(le - le % D)//D-1])


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import sys
    input = sys.stdin.buffer.readline
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]

    dic = {i: (-1, -1) for i in range(1, H*W + 1)}
    for h in range(H):
        for w in range(W):
            dic[A[h][w]] = (h+1, w+1)

    Q = int(input())
    for query in range(Q):
        le, ri = (int(i) for i in input().split())
        cur = 0
        while le != ri:
            i, j = dic[le]
            x, y = dic[le + D]
            cur += abs(x - i) + abs(y - j)
            le = le + D
        print(cur)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]
    num_to_xy = {}
    d_sum = [[] for _ in range(D)]
    for h in range(H):
        for w in range(W):
            num_to_xy[A[h][w]] = (h+1, w+1)
            d_sum[A[h][w] % D].append((A[h][w]))
    for d in range(D):
        d_sum[d].sort()
        cur = []
        y, x = -1, -1
        j, i = -1, -1
        for i, a in enumerate(d_sum[d]):
            if i == 0:
                y, x = num_to_xy[a]
                continue
            j, i = num_to_xy[a]
            cur.append(abs(x - i) + abs(y - j))
            y, x = j, i
        s = [0] * (len(cur) + 1)
        for i in range(0, len(cur)):
            s[i+1] = s[i] + cur[i]
        d_sum[d] = s
    Q = int(input())
    for q in range(Q):
        le, ri = (int(i) for i in input().split())
        if le % D != 0:
            print(d_sum[le % D][(ri - le % D)//D] -
                  d_sum[le % D][(le - le % D)//D])
        else:
            print(d_sum[le % D][(ri - le % D)//D-1] -
                  d_sum[le % D][(le - le % D)//D-1])


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]

    dic = {i: (-1, -1) for i in range(1, H*W + 1)}
    for h in range(H):
        for w in range(W):
            dic[A[h][w]] = (h+1, w+1)

    Q = int(input())
    for query in range(Q):
        le, ri = (int(i) for i in input().split())
        cur = 0
        while le != ri:
            i, j = dic[le]
            x, y = dic[le + D]
            cur += abs(x - i) + abs(y - j)
            le = le + D
        print(cur)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]
    num_to_xy = {}
    d_sum = [[] for _ in range(D)]
    for h in range(H):
        for w in range(W):
            num_to_xy[A[h][w]] = (h+1, w+1)
            d_sum[A[h][w] % D].append((A[h][w]))
    for d in range(D):
        d_sum[d].sort()
        cur = []
        y, x = -1, -1
        j, i = -1, -1
        for i, a in enumerate(d_sum[d]):
            if i == 0:
                y, x = num_to_xy[a]
                continue
            j, i = num_to_xy[a]
            cur.append(abs(x - i) + abs(y - j))
            y, x = j, i
        s = [0] * (len(cur) + 1)
        for i in range(0, len(cur)):
            s[i+1] = s[i] + cur[i]
        d_sum[d] = s
    Q = int(input())
    for q in range(Q):
        le, ri = (int(i) for i in input().split())
        if le % D != 0:
            print(d_sum[le % D][(ri - le % D)//D] -
                  d_sum[le % D][(le - le % D)//D])
        else:
            print(d_sum[le % D][(ri - le % D)//D-1] -
                  d_sum[le % D][(le - le % D)//D-1])


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]
    num_to_xy = {}
    for h in range(H):
        for w in range(W):
            num_to_xy[A[h][w]] = (h+1, w+1)
    Q = int(input())
    for q in range(Q):
        ans = 0
        le, ri = (int(i) for i in input().split())
        while le != ri:
            j, i = num_to_xy[le]
            y, x = num_to_xy[le + D]
            ans += abs(x - i) + abs(y - j)
            le += D
        print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]
    num_to_xy = {}
    d_sum = [[] for _ in range(D)]
    for h in range(H):
        for w in range(W):
            num_to_xy[A[h][w]] = (h+1, w+1)
            d_sum[A[h][w] % D].append((A[h][w]))
    for d in range(D):
        d_sum[d].sort()
        cur = []
        y, x = -1, -1
        j, i = -1, -1
        for i, a in enumerate(d_sum[d]):
            if i == 0:
                y, x = num_to_xy[a]
                continue
            j, i = num_to_xy[a]
            cur.append(abs(x - i) + abs(y - j))
            y, x = j, i
        s = [0] * (len(cur) + 1)
        for i in range(0, len(cur)):
            s[i+1] = s[i] + cur[i]
        d_sum[d] = s
    Q = int(input())
    for q in range(Q):
        le, ri = (int(i) for i in input().split())
        if le % D != 0:
            print(d_sum[le % D][(ri - le % D)//D] -
                  d_sum[le % D][(le - le % D)//D])
        else:
            print(d_sum[le % D][(ri - le % D)//D-1] -
                  d_sum[le % D][(le - le % D)//D-1])


if __name__ == '__main__':
    main()