Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

h,w,d=map(int,input().split())
ans=[0]*(h*w)
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        ans[l[j]-1]=[i,j]
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
for i in range(q):
    s=0
    for j in range(l[i]+d-1,r[i],d):
        s+=abs(ans[j][0]-ans[j-d][0])+abs(ans[j][1]-ans[j-d][1])
    print(s)

Fixed submission:
import sys
input = sys.stdin.readline

h,w,d=map(int,input().split())
A=[0]*(h*w)
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        A[l[j]-1]=[i,j]
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
ans=[0]*(h*w)
for i in range(d,h*w):
    ans[i]=ans[i-d]+abs(A[i][0]-A[i-d][0])+abs(A[i][1]-A[i-d][1])
for i in range(q):
    print(ans[r[i]-1]-ans[l[i]-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

h,w,d=map(int,input().split())
ans=[0]*(h*w)
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        ans[l[j]-1]=[i,j]
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
for i in range(h*w-1,d-1,-1):
    ans[i]=abs(ans[i][0]-ans[i-d][0])+abs(ans[i][1]-ans[i-d][1])
for i in range(d):
    ans[i]=0
for i in range(q):
    print(sum(ans[i] for i in range(l[i]+d-1,r[i],d)))

Fixed submission:
import sys
input = sys.stdin.readline

h,w,d=map(int,input().split())
A=[0]*(h*w)
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        A[l[j]-1]=[i,j]
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
ans=[0]*(h*w)
for i in range(d,h*w):
    ans[i]=ans[i-d]+abs(A[i][0]-A[i-d][0])+abs(A[i][1]-A[i-d][1])
for i in range(q):
    print(ans[r[i]-1]-ans[l[i]-1])

Buggy python submission (verdict: Time Limit Exceeded):
def sol():
    import sys
    input = sys.stdin.readline

    h,w,d=map(int,input().split())
    A=[]
    for i in range(h):
        l=list(map(int,input().split()))
        for j in range(w):
            A.append([l[j],i,j])
    ans=[]
    for i in sorted(A):
        ans.append(i[1:])
    q=int(input())
    l=[0]*q
    r=[0]*q
    for i in range(q):
        l[i],r[i]=map(int,input().split())
    for i in range(h*w-1,d-1,-1):
        ans[i]=abs(ans[i][0]-ans[i-d][0])+abs(ans[i][1]-ans[i-d][1])
    for i in range(d):
        ans[i]=0
    for i in range(q):
        print(sum(ans[i] for i in range(l[i]+d-1,r[i],d)))
sol()

Fixed submission:
import sys
input = sys.stdin.readline

h,w,d=map(int,input().split())
A=[0]*(h*w)
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        A[l[j]-1]=[i,j]
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
ans=[0]*(h*w)
for i in range(d,h*w):
    ans[i]=ans[i-d]+abs(A[i][0]-A[i-d][0])+abs(A[i][1]-A[i-d][1])
for i in range(q):
    print(ans[r[i]-1]-ans[l[i]-1])

Buggy python submission (verdict: Time Limit Exceeded):
def sol():
    import sys
    input = sys.stdin.readline

    h,w,d=map(int,input().split())
    A=[]
    for i in range(h):
        l=list(map(int,input().split()))
        for j in range(w):
            A.append([l[j],i,j])
    ans=[]
    for i in sorted(A):
        ans.append(i[1:])
    q=int(input())
    l=[0]*q
    r=[0]*q
    for i in range(q):
        l[i],r[i]=map(int,input().split())
    for i in range(h*w-1,d-1,-1):
        ans[i]=abs(ans[i][0]-ans[i-d][0])+abs(ans[i][1]-ans[i-d][1])
    for i in range(d):
        ans[i]=0
    for i in range(q):
        print(sum(ans[i] for i in range(l[i]+d-1,r[i],d)))
sol()

Fixed submission:
import sys
input = sys.stdin.readline

h,w,d=map(int,input().split())
A=[0]*(h*w)
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        A[l[j]-1]=[i,j]
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
ans=[0]*(h*w)
for i in range(d,h*w):
    ans[i]=ans[i-d]+abs(A[i][0]-A[i-d][0])+abs(A[i][1]-A[i-d][1])
for i in range(q):
    print(ans[r[i]-1]-ans[l[i]-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

h,w,d=map(int,input().split())
A=[]
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        A.append([l[j],i,j])
ans=[]
for i in sorted(A):
    ans.append(i[1:])
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
for i in range(h*w-1,d-1,-1):
    ans[i]=abs(ans[i][0]-ans[i-d][0])+abs(ans[i][1]-ans[i-d][1])
for i in range(d):
    ans[i]=0
for i in range(q):
    print(sum(ans[i] for i in range(l[i]+d-1,r[i],d)))

Fixed submission:
import sys
input = sys.stdin.readline

h,w,d=map(int,input().split())
A=[0]*(h*w)
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        A[l[j]-1]=[i,j]
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
ans=[0]*(h*w)
for i in range(d,h*w):
    ans[i]=ans[i-d]+abs(A[i][0]-A[i-d][0])+abs(A[i][1]-A[i-d][1])
for i in range(q):
    print(ans[r[i]-1]-ans[l[i]-1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from heapq import heappush,heappop

h,w,d=map(int,input().split())
a=[list(map(int,input().split())) for _ in [0]*h]
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
A=[]
for i in range(h):
    for j in range(w):
        heappush(A,[a[i][j],i,j])
ans=[]
for i in range(h*w):
    ans.append(heappop(A)[1:])
for i in range(h*w-1,d-1,-1):
    ans[i]=abs(ans[i][0]-ans[i-d][0])+abs(ans[i][1]-ans[i-d][1])
for i in range(d):
    ans[i]=0
for i in range(q):
    print(sum(ans[i] for i in range(l[i]+d-1,r[i],d)))

Fixed submission:
import sys
input = sys.stdin.readline

h,w,d=map(int,input().split())
A=[0]*(h*w)
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        A[l[j]-1]=[i,j]
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())
ans=[0]*(h*w)
for i in range(d,h*w):
    ans[i]=ans[i-d]+abs(A[i][0]-A[i-d][0])+abs(A[i][1]-A[i-d][1])
for i in range(q):
    print(ans[r[i]-1]-ans[l[i]-1])