Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = map(int, input().split())
A_where = [0] * (H*W+1)
A_where[0] = (-1, -1)
for p in range(H):
    A = tuple(map(int, input().split()))
    for q in range(W):
        A_where[A[q]] = (p, q)

Q = int(input())
Exam = []
maxD = 0
for i in range(Q):
    l, r = map(int, input().split())
    maxD = max(maxD, (r-l))
    Exam.append((l,r))

DP = [[0] * (H*W+1) for _ in range(H*W+1)]

for w in range(D, maxD+1, D):
    for start in range(H*W+1-w):
        if start + w > H*W:
            continue
        if w == D:
            y1, x1 = A_where[start]
            y2, x2 = A_where[start + w]
            DP[start][start+w] = abs(y1-y2) + abs(x1-x2)
        else:
            DP[start][start+w] = DP[start][start+w-D] + DP[start+w-D][start+w]

for l, r in Exam:
    print(DP[l][r])

Fixed submission:
H, W, D = map(int, input().split())
A_where = [0] * (H*W+1)
A_where[0] = (-1, -1)
for p in range(H):
    A = list(map(int, input().split()))
    for q in range(W):
        A_where[A[q]] = (p, q)

Q = int(input())

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

for i in range(D+1, H*W+1):
    y1, x1 = A_where[i]
    y2, x2 = A_where[i-D]

    DP[i] = DP[i-D] + abs(y1-y2) + abs(x1-x2)

for i in range(Q):
    l, r = map(int, input().split())
    print(DP[r] - DP[l])

Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = map(int, input().split())
A_where = [0] * (H*W+1)
A_where[0] = (-1, -1)
for p in range(H):
    A = list(map(int, input().split()))
    for q in range(W):
        A_where[A[q]] = (p, q)

Q = int(input())

DP = [[0] * (H*W+1) for _ in range(H*W+1)]

for w in range(D, H*W, D):
    for start in range(H*W+1-w):
        if start + w > H*W:
            continue
        if w == D:
            y1, x1 = A_where[start]
            y2, x2 = A_where[start + w]
            DP[start][start+w] = abs(y1-y2) + abs(x1-x2)
        else:
            DP[start][start+w] = DP[start][start+w-D] + DP[start+w-D][start+w]

for i in range(Q):
    l, r = map(int, input().split())
    print(DP[l][r])

Fixed submission:
H, W, D = map(int, input().split())
A_where = [0] * (H*W+1)
A_where[0] = (-1, -1)
for p in range(H):
    A = list(map(int, input().split()))
    for q in range(W):
        A_where[A[q]] = (p, q)

Q = int(input())

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

for i in range(D+1, H*W+1):
    y1, x1 = A_where[i]
    y2, x2 = A_where[i-D]

    DP[i] = DP[i-D] + abs(y1-y2) + abs(x1-x2)

for i in range(Q):
    l, r = map(int, input().split())
    print(DP[r] - DP[l])

Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = map(int, input().split())
A_where = [0] * (H*W+1)
A_where[0] = (-1, -1)
for p in range(H):
    A = list(map(int, input().split()))
    for q in range(W):
        A_where[A[q]] = (p, q)

Q = int(input())

DP = [[0] * (H*W+1) for _ in range(H*W+1)]

for w in range(D, H*W, D):
    for start in range(H*W+1):
        if start + w > H*W:
            continue
        if w == D:
            y1, x1 = A_where[start]
            y2, x2 = A_where[start + w]
            DP[start][start+w] = abs(y1-y2) + abs(x1-x2)
        else:
            DP[start][start+w] = DP[start][start+w-D] + DP[start+w-D][start+w]

for i in range(Q):
    l, r = map(int, input().split())
    print(DP[l][r])



Fixed submission:
H, W, D = map(int, input().split())
A_where = [0] * (H*W+1)
A_where[0] = (-1, -1)
for p in range(H):
    A = list(map(int, input().split()))
    for q in range(W):
        A_where[A[q]] = (p, q)

Q = int(input())

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

for i in range(D+1, H*W+1):
    y1, x1 = A_where[i]
    y2, x2 = A_where[i-D]

    DP[i] = DP[i-D] + abs(y1-y2) + abs(x1-x2)

for i in range(Q):
    l, r = map(int, input().split())
    print(DP[r] - DP[l])

Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = map(int, input().split())
A_where = [0] * (H*W+1)
A_where[0] = (-1, -1)
for p in range(H):
    A = list(map(int, input().split()))
    for q in range(W):
        A_where[A[q]] = (p, q)

Q = int(input())

DP = [0] * (H*W+1)
for _ in range(Q):
    ans = 0
    start, end = map(int, input().split())
    while start != end:
        next = start + D
        if DP[start] > 0:
            ans += DP[start]
        else:
            ny, nx = A_where[next]
            y, x = A_where[start]
            an = abs(ny-y) + abs(nx-x)
            DP[start] = an
            ans += an
            start = next
    print(ans)

Fixed submission:
H, W, D = map(int, input().split())
A_where = [0] * (H*W+1)
A_where[0] = (-1, -1)
for p in range(H):
    A = list(map(int, input().split()))
    for q in range(W):
        A_where[A[q]] = (p, q)

Q = int(input())

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

for i in range(D+1, H*W+1):
    y1, x1 = A_where[i]
    y2, x2 = A_where[i-D]

    DP[i] = DP[i-D] + abs(y1-y2) + abs(x1-x2)

for i in range(Q):
    l, r = map(int, input().split())
    print(DP[r] - DP[l])

Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = map(int, input().split())
A = []
for _ in range(H):
    A.append(list(map(int, input().split())))
A_where = [(-1, -1)]
for i in range(1, H*W+1):
    for j in range(H):
        for k in range(W):
            if A[j][k] == i:
                A_where.append((j, k))

Q = int(input())

DP = [0] * (H*W+1)
for _ in range(Q):
    ans = 0
    start, end = map(int, input().split())
    while start != end:
        next = start + D
        if DP[start] > 0:
            ans += DP[start]
        else:
            ny, nx = A_where[next]
            y, x = A_where[start]
            an = abs(ny-y) + abs(nx-x)
            DP[start] = an
            ans += an
            start = next
    print(ans)

Fixed submission:
H, W, D = map(int, input().split())
A_where = [0] * (H*W+1)
A_where[0] = (-1, -1)
for p in range(H):
    A = list(map(int, input().split()))
    for q in range(W):
        A_where[A[q]] = (p, q)

Q = int(input())

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

for i in range(D+1, H*W+1):
    y1, x1 = A_where[i]
    y2, x2 = A_where[i-D]

    DP[i] = DP[i-D] + abs(y1-y2) + abs(x1-x2)

for i in range(Q):
    l, r = map(int, input().split())
    print(DP[r] - DP[l])