Buggy python submission (verdict: Runtime Error):
def main():
    import sys
    sys.setrecursionlimit(10000)
    h, w, d = map(int, input().split())
    p = []
    for i in range(1, h + 1):
        l = map(int, input().split())
        for j, k in enumerate(l, 1):
            p.append((k, (i, j)))
    p.sort(key=lambda x: x[0])

    q = int(input())

    dist = [0] * (w * h + 1)

    def Q(i, c, x, y):
        if i + d > w * h:
            return
        _, (nx, ny) = p[i + d - 1]
        nc = c + abs(nx - x) + abs(ny - y)
        dist[i + d] = nc
        Q(i + d, nc, nx, ny)

    for i in range(d):
        n, (x, y) = p[i]
        Q(n, 0, x, y)

    res = []
    for _ in range(q):
        l, r = map(int, input().split())
        res.append(dist[r] - dist[l])

    ans = '\n'.join(map(str, res))
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    from itertools import accumulate
    h, w, d = map(int, input().split())

    a = [0] * (h * w + 1)
    b = [0] * (h * w + 1)
    for i in range(1, h + 1):
        l = map(int, input().split())
        for j, k in enumerate(l, 1):
            a[k] = i
            b[k] = j

    c = [0] * (h * w + 1)
    for i in range(d + 1, h * w + 1):
        c[i] = c[i - d] + abs(a[i] - a[i - d]) + abs(b[i] - b[i - d])

    q = int(input())
    res = []
    for _ in range(q):
        l, r = map(int, input().split())
        res.append(c[r] - c[l])

    ans = '\n'.join(map(str, res))
    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
def main():
    from itertools import accumulate
    h, w, d = map(int, input().split())
    p = []
    for i in range(1, h + 1):
        l = map(int, input().split())
        for j, k in enumerate(l, 1):
            p.append((k, (i, j)))
    p.sort(key=lambda x: x[0])

    q = int(input())

    dist = [0] * (w * h + 1)

    def Q(i, c, x, y):
        if i + d > w * h:
            return
        _, (nx, ny) = p[i + d - 1]
        nc = c + abs(nx - x) + abs(ny - y)
        dist[i + d] = nc
        Q(i + d, nc, nx, ny)

    for i in range(d):
        n, (x, y) = p[i]
        Q(n, 0, x, y)

    res = []
    for _ in range(q):
        l, r = map(int, input().split())
        res.append(dist[r] - dist[l])

    ans = '\n'.join(map(str, res))
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    from itertools import accumulate
    h, w, d = map(int, input().split())

    a = [0] * (h * w + 1)
    b = [0] * (h * w + 1)
    for i in range(1, h + 1):
        l = map(int, input().split())
        for j, k in enumerate(l, 1):
            a[k] = i
            b[k] = j

    c = [0] * (h * w + 1)
    for i in range(d + 1, h * w + 1):
        c[i] = c[i - d] + abs(a[i] - a[i - d]) + abs(b[i] - b[i - d])

    q = int(input())
    res = []
    for _ in range(q):
        l, r = map(int, input().split())
        res.append(c[r] - c[l])

    ans = '\n'.join(map(str, res))
    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from functools import lru_cache
    h, w, d = map(int, input().split())

    a = []
    for i in range(1, h + 1):
        l = map(int, input().split())
        for j, k in enumerate(l, 1):
            a.append((k, (i, j)))

    a.sort(key=lambda x: x[0])

    q = int(input())

    @lru_cache(maxsize=q)
    def Q(l, r):
        _, (x, y) = a[l - 1]

        s = 0
        for k, (i, j) in a[l - 1::d]:
            s += abs(x - i) + abs(y - j)
            if r == k:
                break
            x, y = i, j
        return s

    res = []
    for _ in range(q):
        l, r = map(int, input().split())
        s = Q(l, r)
        res.append(s)

    ans = '\n'.join(map(str, res))
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    from itertools import accumulate
    h, w, d = map(int, input().split())

    a = [0] * (h * w + 1)
    b = [0] * (h * w + 1)
    for i in range(1, h + 1):
        l = map(int, input().split())
        for j, k in enumerate(l, 1):
            a[k] = i
            b[k] = j

    c = [0] * (h * w + 1)
    for i in range(d + 1, h * w + 1):
        c[i] = c[i - d] + abs(a[i] - a[i - d]) + abs(b[i] - b[i - d])

    q = int(input())
    res = []
    for _ in range(q):
        l, r = map(int, input().split())
        res.append(c[r] - c[l])

    ans = '\n'.join(map(str, res))
    print(ans)


if __name__ == '__main__':
    main()