Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=map(int,input().split())
A=[]

for h in range(H):
    A.append(list(map(int,input().split())))

pos= {}
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=[h,w]

def mp(a,b):
    if a==b:
        return 0
    else:
        ah,aw=pos[a]
        bh,bw=pos[b]
        ret=abs(ah-bh)+abs(aw-bw)
        return ret

dis=[[0]*H*W for _ in range(H*W)]
def rec(a,b):
    if a==b:
        return 0
    if dis[a-1][b-1]!=0:
        return dis[a-1][b-1]
    else:
        if dis[b-1-D][b-1]!=0:
            return rec(a,b-D)+mp(b-D,b)
        else:
            return mp(a,a+D)+rec(a+D,b)



Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    ans=rec(L,R)
    print(ans)


Fixed submission:
H,W,D=map(int,input().split())
A=[]

for h in range(H):
    A.append(list(map(int,input().split())))

pos= {}
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=[h,w]

S=[0]*(H*W)
for d in range(D):
    tmp=0
    now=d+1
    while now+D<=H*W:
        nowh,noww=pos[now]
        newh,neww=pos[now+D]
        tmp+=abs(nowh-newh)+abs(noww-neww)
        S[now+D-1]=tmp
        now+=D

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

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=map(int,input().split())
A=[]

for h in range(H):
    A.append(list(map(int,input().split())))

pos= {}
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=[h,w]



Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    nowh,noww=pos[L]
    now=L
    ans=0
    while now<R:
        newh,neww=pos[now+D]
        ans+=abs(nowh-newh)+abs(noww-neww)
        now+=D
        nowh=newh
        noww=neww
    print(ans)


Fixed submission:
H,W,D=map(int,input().split())
A=[]

for h in range(H):
    A.append(list(map(int,input().split())))

pos= {}
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=[h,w]

S=[0]*(H*W)
for d in range(D):
    tmp=0
    now=d+1
    while now+D<=H*W:
        nowh,noww=pos[now]
        newh,neww=pos[now+D]
        tmp+=abs(nowh-newh)+abs(noww-neww)
        S[now+D-1]=tmp
        now+=D

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

Buggy python submission (verdict: Time Limit Exceeded):

import sys
sys.setrecursionlimit(10000000)
H,W,D=map(int,input().split())

dic={}
A=[]
for h in range(H):
    A.append(list(map(int,input().split())))
    for w in range(W):
        dic[A[h][w]]=[h,w]

Q=int(input())

c=[[-1]*(H*W+1) for _ in range(H*W+1)]

for i in range(H*W+1):
    c[i][i]=0

def rec(a,b):
    if c[a][b]!=-1:
        return c[a][b]
    y,x=dic[a]
    ny,nx=dic[a+D]
    ret=abs(y-ny)+abs(x-nx)+rec(a+D,b)
    c[a][b]=ret
    return ret

for i in range(Q):
    L,R=map(int,input().split())
    ans=rec(L,R)
    print(ans)

Fixed submission:
H,W,D=map(int,input().split())
A=[]

for h in range(H):
    A.append(list(map(int,input().split())))

pos= {}
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=[h,w]

S=[0]*(H*W)
for d in range(D):
    tmp=0
    now=d+1
    while now+D<=H*W:
        nowh,noww=pos[now]
        newh,neww=pos[now+D]
        tmp+=abs(nowh-newh)+abs(noww-neww)
        S[now+D-1]=tmp
        now+=D

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

Buggy python submission (verdict: Time Limit Exceeded):

H,W,D=map(int,input().split())

dic={}
A=[]
for h in range(H):
    A.append(list(map(int,input().split())))
    for w in range(W):
        dic[A[h][w]]=[h,w]

Q=int(input())

c=[-1]*(H*W+1)

def rec(n):
    if c[n]!=-1:
        return c[n]
    y,x=dic[n]
    ny,nx=dic[n+D]
    ret=abs(y-ny)+abs(x-nx)
    c[n]=ret
    return ret

for i in range(Q):
    L,R=map(int,input().split())
    N=(R-L)//D
    ans=0
    for j in range(N):
        ans+=rec(L+D*j)
    print(ans)

Fixed submission:
H,W,D=map(int,input().split())
A=[]

for h in range(H):
    A.append(list(map(int,input().split())))

pos= {}
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=[h,w]

S=[0]*(H*W)
for d in range(D):
    tmp=0
    now=d+1
    while now+D<=H*W:
        nowh,noww=pos[now]
        newh,neww=pos[now+D]
        tmp+=abs(nowh-newh)+abs(noww-neww)
        S[now+D-1]=tmp
        now+=D

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

Buggy python submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10**9)


H,W,D=map(int,input().split())

dic={}
A=[]
for h in range(H):
    A.append(list(map(int,input().split())))
    for w in range(W):
        dic[A[h][w]]=[h,w]

Q=int(input())

c=[-1]*(H*W+1)
def rec(n):
    if c[n]!=-1:
        return [c[n]]
    y,x=dic[n]
    ny,nx=dic[n+D]
    ret=abs(y-ny)+abs(x-nx)
    c[n]=ret
    return ret

for i in range(Q):
    L,R=map(int,input().split())
    N=(R-L)//D
    ans=0
    for j in range(N):
        ans+=rec(L+D*j)
    print(ans)

Fixed submission:
H,W,D=map(int,input().split())
A=[]

for h in range(H):
    A.append(list(map(int,input().split())))

pos= {}
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=[h,w]

S=[0]*(H*W)
for d in range(D):
    tmp=0
    now=d+1
    while now+D<=H*W:
        nowh,noww=pos[now]
        newh,neww=pos[now+D]
        tmp+=abs(nowh-newh)+abs(noww-neww)
        S[now+D-1]=tmp
        now+=D

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

Buggy python submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10**5)


H,W,D=map(int,input().split())

dic={}
A=[]
for h in range(H):
    A.append(list(map(int,input().split())))
    for w in range(W):
        dic[A[h][w]]=[h,w]

Q=int(input())

c=[-1]*(H*W+1)
def rec(n):
    if c[n]!=-1:
        return [c[n]]
    y,x=dic[n]
    ny,nx=dic[n+D]
    ret=abs(y-ny)+abs(x-nx)
    c[n]=ret
    return ret

for i in range(Q):
    L,R=map(int,input().split())
    N=(R-L)//D
    ans=0
    for j in range(N):
        ans+=rec(L+D*j)
    print(ans)

Fixed submission:
H,W,D=map(int,input().split())
A=[]

for h in range(H):
    A.append(list(map(int,input().split())))

pos= {}
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=[h,w]

S=[0]*(H*W)
for d in range(D):
    tmp=0
    now=d+1
    while now+D<=H*W:
        nowh,noww=pos[now]
        newh,neww=pos[now+D]
        tmp+=abs(nowh-newh)+abs(noww-neww)
        S[now+D-1]=tmp
        now+=D

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

Buggy python submission (verdict: Runtime Error):
H,W,D=map(int,input().split())

dic={}
A=[]
for h in range(H):
    A.append(list(map(int,input().split())))
    for w in range(W):
        dic[A[h][w]]=[h,w]

Q=int(input())

c=[-1]*(H*W+1)
def rec(n):
    if c[n]!=-1:
        return [c[n]]
    y,x=dic[n]
    ny,nx=dic[n+D]
    ret=abs(y-ny)+abs(x-nx)
    c[n]=ret
    return ret

for i in range(Q):
    L,R=map(int,input().split())
    N=(R-L)//D
    ans=0
    for j in range(N):
        ans+=rec(L+D*j)
    print(ans)

Fixed submission:
H,W,D=map(int,input().split())
A=[]

for h in range(H):
    A.append(list(map(int,input().split())))

pos= {}
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=[h,w]

S=[0]*(H*W)
for d in range(D):
    tmp=0
    now=d+1
    while now+D<=H*W:
        nowh,noww=pos[now]
        newh,neww=pos[now+D]
        tmp+=abs(nowh-newh)+abs(noww-neww)
        S[now+D-1]=tmp
        now+=D

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

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=map(int,input().split())

dic={}
A=[]
for h in range(H):
    A.append(list(map(int,input().split())))
    for w in range(W):
        dic[A[h][w]]=[h,w]

Q=int(input())

for i in range(Q):
    L,R=map(int,input().split())
    y,x=dic[L]
    ans=0
    while A[y][x]!=R:
        ny,nx=dic[A[y][x]+D]
        ans+=abs(y-ny)+abs(x-nx)
        y=ny
        x=nx
    print(ans)

Fixed submission:
H,W,D=map(int,input().split())
A=[]

for h in range(H):
    A.append(list(map(int,input().split())))

pos= {}
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=[h,w]

S=[0]*(H*W)
for d in range(D):
    tmp=0
    now=d+1
    while now+D<=H*W:
        nowh,noww=pos[now]
        newh,neww=pos[now+D]
        tmp+=abs(nowh-newh)+abs(noww-neww)
        S[now+D-1]=tmp
        now+=D

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

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=map(int,input().split())

dic={}
A=[]
for h in range(H):
    A.append(list(map(int,input().split())))
    for w in range(W):
        dic[A[h][w]]=[h,w]

Q=int(input())

for i in range(Q):
    L,R=map(int,input().split())
    y,x=dic[L]
    ans=0
    while A[y][x]!=R:
        ny,nx=dic[A[y][x]+D]
        ans+=abs(y-ny)+abs(x-nx)
        y=ny
        x=nx
    print(ans)

Fixed submission:
H,W,D=map(int,input().split())
A=[]

for h in range(H):
    A.append(list(map(int,input().split())))

pos= {}
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=[h,w]

S=[0]*(H*W)
for d in range(D):
    tmp=0
    now=d+1
    while now+D<=H*W:
        nowh,noww=pos[now]
        newh,neww=pos[now+D]
        tmp+=abs(nowh-newh)+abs(noww-neww)
        S[now+D-1]=tmp
        now+=D

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