Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=list(map(int,input().split()))
arr=[0 for i in range(H*W+1)]
for y in range(H):
    for x,n in enumerate(map(int,input().split())):
        arr[n]=[x,y]

dic={}

Q=int(input())
for i in range(Q):
    ans=0
    now,goal= list(map(int,input().split()))
    nx=arr[now][0]
    ny=arr[now][1]
    tmp=now
    for j in range((goal-now)//D):
        if dic.get(tmp*H*W+goal,0)!=0:
            dic[now*H*W+goal]=ans+dic[tmp*H*W+goal]
            break
        tmp+=D
        x=arr[tmp][0]
        y=arr[tmp][1]
        ans+=abs(x-nx)+abs(y-ny)
        nx=x
        ny=y
        dic[now*H*W+tmp]=ans
    print(dic.get(now*H*W+goal,0))

Fixed submission:
H,W,D=list(map(int,input().split()))
map_=[[0,0] for _ in range(H*W+1)]
for y in range(H):
    for x,A in enumerate(map(int,input().split())):
        map_[A]=[x+1,y+1]

cost=[0 for _ in range(H*W+1)]
for i in range(D+1,H*W+1):
    cost[i]+=abs(map_[i][0]-map_[i-D][0])+abs(map_[i][1]-map_[i-D][1])+cost[i-D]
Q=int(input())
for i in range(Q):
    L,R=list(map(int,input().split()))
    print(cost[R]-cost[L])

Buggy python submission (verdict: Runtime Error):
H,W,D=list(map(int,input().split()))
arr=[0 for i in range(H*W+1)]
for y in range(H):
    for x,n in enumerate(map(int,input().split())):
        arr[n]=[x,y]

dic={}

Q=int(input())
for i in range(Q):
    ans=0
    now,goal= list(map(int,input().split()))
    nx=arr[now][0]
    ny=arr[now][1]
    tmp=now
    for j in range((goal-now)//D):
        if dic.get(tmp*H*W+goal,0)!=0:
            dic[now*H*W+goal]=ans+dic[tmp*H*W+goal]
            break
        tmp+=D
        x=arr[tmp][0]
        y=arr[tmp][1]
        ans+=abs(x-nx)+abs(y-ny)
        nx=x
        ny=y
        dic[now*H*W+tmp]=ans
    print(dic[now*H*W+goal])

Fixed submission:
H,W,D=list(map(int,input().split()))
map_=[[0,0] for _ in range(H*W+1)]
for y in range(H):
    for x,A in enumerate(map(int,input().split())):
        map_[A]=[x+1,y+1]

cost=[0 for _ in range(H*W+1)]
for i in range(D+1,H*W+1):
    cost[i]+=abs(map_[i][0]-map_[i-D][0])+abs(map_[i][1]-map_[i-D][1])+cost[i-D]
Q=int(input())
for i in range(Q):
    L,R=list(map(int,input().split()))
    print(cost[R]-cost[L])

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=list(map(int,input().split()))
arr=[0 for i in range(H*W+1)]
for y in range(H):
    for x,n in enumerate(map(int,input().split())):
        arr[n]=[x,y]

dic={}

Q=int(input())
for i in range(Q):
    ans=0
    now,goal= list(map(int,input().split()))
    nx=arr[now][0]
    ny=arr[now][1]
    tmp=now
    for j in range((goal-now)//D):
        if dic.get(tmp*H*W+goal,0)!=0:
            dic[now*H*W+goal]=ans+dic[tmp*H*W+goal]
            print(dic[now*H*W+goal])
            break
        tmp+=D
        x=arr[tmp][0]
        y=arr[tmp][1]
        ans+=abs(x-nx)+abs(y-ny)
        nx=x
        ny=y
    if dic.get(now*H*W+goal,0)==0:
        dic[now*H*W+goal]=ans
        print(ans)

Fixed submission:
H,W,D=list(map(int,input().split()))
map_=[[0,0] for _ in range(H*W+1)]
for y in range(H):
    for x,A in enumerate(map(int,input().split())):
        map_[A]=[x+1,y+1]

cost=[0 for _ in range(H*W+1)]
for i in range(D+1,H*W+1):
    cost[i]+=abs(map_[i][0]-map_[i-D][0])+abs(map_[i][1]-map_[i-D][1])+cost[i-D]
Q=int(input())
for i in range(Q):
    L,R=list(map(int,input().split()))
    print(cost[R]-cost[L])

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=list(map(int,input().split()))
arr=[0 for i in range(H*W+1)]
for y in range(H):
    for x,n in enumerate(map(int,input().split())):
        arr[n]=[x,y]

dic={}

Q=int(input())
for i in range(Q):
    ans=0
    now,goal= list(map(int,input().split()))
    nx=arr[now][0]
    ny=arr[now][1]
    if dic.get(now*H*W+goal,0)!=0:
        print(dic[now*H*W+goal])
        continue
    tmp=now
    for j in range((goal-now)//D):
        tmp+=D
        x=arr[tmp][0]
        y=arr[tmp][1]
        ans+=abs(x-nx)+abs(y-ny)
        nx=x
        ny=y
    dic[now*H*W+goal]=ans
    print(ans)

Fixed submission:
H,W,D=list(map(int,input().split()))
map_=[[0,0] for _ in range(H*W+1)]
for y in range(H):
    for x,A in enumerate(map(int,input().split())):
        map_[A]=[x+1,y+1]

cost=[0 for _ in range(H*W+1)]
for i in range(D+1,H*W+1):
    cost[i]+=abs(map_[i][0]-map_[i-D][0])+abs(map_[i][1]-map_[i-D][1])+cost[i-D]
Q=int(input())
for i in range(Q):
    L,R=list(map(int,input().split()))
    print(cost[R]-cost[L])

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=list(map(int,input().split()))
arr=[0 for i in range(H*W+1)]
for y in range(H):
    for x,n in enumerate(map(int,input().split())):
        arr[n]=[x,y]

dic={}

Q=int(input())
for i in range(Q):
    ans=0
    now,goal= list(map(int,input().split()))
    nx=arr[now][0]
    ny=arr[now][1]
    if dic.get(now*H*W+goal,0)!=0:
        print(ans)
        continue
    for j in range((goal-now)//D):
        now+=D
        x=arr[now][0]
        y=arr[now][1]
        ans+=abs(x-nx)+abs(y-ny)
        nx=x
        ny=y
    dic[now*H*W+goal]=ans
    print(ans)

Fixed submission:
H,W,D=list(map(int,input().split()))
map_=[[0,0] for _ in range(H*W+1)]
for y in range(H):
    for x,A in enumerate(map(int,input().split())):
        map_[A]=[x+1,y+1]

cost=[0 for _ in range(H*W+1)]
for i in range(D+1,H*W+1):
    cost[i]+=abs(map_[i][0]-map_[i-D][0])+abs(map_[i][1]-map_[i-D][1])+cost[i-D]
Q=int(input())
for i in range(Q):
    L,R=list(map(int,input().split()))
    print(cost[R]-cost[L])