Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
INF = float('inf')
H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]

d = defaultdict(lambda:[])

for i in range(H):
    for j in range(W):
        d[A[i][j]] = [i,j]

cost = defaultdict(lambda:[])
for r in range(1,D+1):
    for m in range(0,H*W//D):
        if D*(m+1)+r <= H*W:
            cost[r].append(abs(d[D*m+r][0]-d[D*(m+1)+r][0])+abs(d[D*m+r][1]-d[D*(m+1)+r][1]))
for r in range(1,D+1):
    for m in range(len(cost[r])-1):
        cost[r][m+1] += cost[r][m]

Q = int(input())

def magic(L,R):
    r = L%D
    if r == 0:
        r = D
    ml = (L-r)//D
    mr = (R-r)//D
    res = cost[r][mr-1]
    if ml != 0:
        res -= cost[r][ml-1]
    return res


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

Fixed submission:
H,W,D = map(int,input().split())
d = {}
for i in range(H):
    A = list(map(int,input().split()))
    for j in range(W):
        d[A[j]] = (i,j)
m = []
for i in range(1,D+1):
    mm = [0]
    for j in range(i+D,H*W+1,D):
        k = (j-i)//D
        dd = mm[k-1]+abs(d[j][0]-d[j-D][0])+abs(d[j][1]-d[j-D][1])
        mm.append(dd)
    m.append(mm)
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    if L%D != 0:
        mm = m[L%D-1]
        Lq = L//D
        Rq = R//D
        print(mm[Rq]-mm[Lq])
    else:
        mm = m[D-1]
        Lq = L//D
        Rq = R//D
        print(mm[Rq-1]-mm[Lq-1])

Buggy python submission (verdict: Runtime Error):
H,W,D = map(int,input().split())
d = {}
for i in range(H):
    A = list(map(int,input().split()))
    for j in range(W):
        d[A[j]] = (i,j)
m = []
for i in range(1,D+1):
    mm = [0]
    for j in range(i+D,H*W,D):
        k = (j-i)//D
        dd = mm[k-1]+abs(d[j][0]-d[j-D][0])+abs(d[j][1]-d[j-D][1])
        mm.append(dd)
    m.append(mm)
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    if L%D != 0:
        mm = m[L%D-1]
        Lq = L//D
        Rq = R//D
        print(mm[Rq]-mm[Lq])
    else:
        mm = m[D-1]
        Lq = L//D
        Rq = R//D
        print(mm[Rq-1]-mm[Lq-1])

Fixed submission:
H,W,D = map(int,input().split())
d = {}
for i in range(H):
    A = list(map(int,input().split()))
    for j in range(W):
        d[A[j]] = (i,j)
m = []
for i in range(1,D+1):
    mm = [0]
    for j in range(i+D,H*W+1,D):
        k = (j-i)//D
        dd = mm[k-1]+abs(d[j][0]-d[j-D][0])+abs(d[j][1]-d[j-D][1])
        mm.append(dd)
    m.append(mm)
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    if L%D != 0:
        mm = m[L%D-1]
        Lq = L//D
        Rq = R//D
        print(mm[Rq]-mm[Lq])
    else:
        mm = m[D-1]
        Lq = L//D
        Rq = R//D
        print(mm[Rq-1]-mm[Lq-1])

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D = map(int,input().split())
d = {}
for i in range(H):
    A = list(map(int,input().split()))
    for j in range(W):
        d[A[j]] = (i,j)
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    if L == R:
        print(0)
    else:
        ans = 0
        while L < R:
            ans += abs(d[L+D][0]-d[L][0])+abs(d[L+D][1]-d[L][1])
            L+=D
        print(ans)

Fixed submission:
H,W,D = map(int,input().split())
d = {}
for i in range(H):
    A = list(map(int,input().split()))
    for j in range(W):
        d[A[j]] = (i,j)
m = []
for i in range(1,D+1):
    mm = [0]
    for j in range(i+D,H*W+1,D):
        k = (j-i)//D
        dd = mm[k-1]+abs(d[j][0]-d[j-D][0])+abs(d[j][1]-d[j-D][1])
        mm.append(dd)
    m.append(mm)
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    if L%D != 0:
        mm = m[L%D-1]
        Lq = L//D
        Rq = R//D
        print(mm[Rq]-mm[Lq])
    else:
        mm = m[D-1]
        Lq = L//D
        Rq = R//D
        print(mm[Rq-1]-mm[Lq-1])