Buggy python submission (verdict: Time Limit Exceeded):
h,w,d=map(int,input().split())
D=dict()
for i in range(h):
  A=[int(i) for i in input().split()]
  for j in range(w):
    D[A[j]]=[i+1,j+1]
def Dist(x,y):
  return abs(D[x][0]-D[y][0])+abs(D[x][1]-D[y][1])
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  ans=0
  rep=(r-l)//d
  for j in range(rep):
    ans+=Dist(l+j*d,l+(j+1)*d)
  print(ans)


Fixed submission:
h,w,d=map(int,input().split())
D=dict()
for i in range(h):
  A=[int(i) for i in input().split()]
  for j in range(w):
    D[A[j]]=[i+1,j+1]
def Dist(x,y):
  return abs(D[x][0]-D[y][0])+abs(D[x][1]-D[y][1])
T=[[0 for _ in range((h*w)//d)] for _ in range(d)]
for i in range(d):
  for j in range((h*w)//d):
    if i+1+d*(j+1)>h*w:
      continue
    elif j==0:
      T[i][j]=Dist(i+1,i+1+d)
    else:  
      T[i][j]=T[i][j-1]+Dist(i+1+d*j,i+1+d*(j+1))
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  x=l%d
  if r==x:
    print(0)
  elif l==x and x!=0:
    print(T[x-1][(r-x)//d-1])
  elif l==x and x==0:
    print(T[x-1][(r-x)//d-2])
  else:
    ll=(l-x)//d-1
    rr=(r-x)//d-1
    if x==0:
      ll-=1
      rr-=1
    print(T[x-1][rr]-T[x-1][ll])

Buggy python submission (verdict: Runtime Error):
h,w,d=map(int,input().split())
D=dict()
for i in range(h):
  A=[int(i) for i in input().split()]
  for j in range(w):
    D[A[j]]=[i+1,j+1]
def Dist(x,y):
  return abs(D[x][0]-D[y][0])+abs(D[x][1]-D[y][1])
T=[[0 for _ in range(h*w)] for _ in range(h*w)]
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  ans=0
  rep=(r-l)//d
  for j in range(rep):
    if T[l+j*d][l+(j+1)*d]!=0:
      ans+=T[l+j*d][l+(j+1)*d]
    else:
      ans+=Dist(l+j*d,l+(j+1)*d)
      T[l+j*d][l+(j+1)*d]=Dist(l+j*d,l+(j+1)*d)
  print(ans)

Fixed submission:
h,w,d=map(int,input().split())
D=dict()
for i in range(h):
  A=[int(i) for i in input().split()]
  for j in range(w):
    D[A[j]]=[i+1,j+1]
def Dist(x,y):
  return abs(D[x][0]-D[y][0])+abs(D[x][1]-D[y][1])
T=[[0 for _ in range((h*w)//d)] for _ in range(d)]
for i in range(d):
  for j in range((h*w)//d):
    if i+1+d*(j+1)>h*w:
      continue
    elif j==0:
      T[i][j]=Dist(i+1,i+1+d)
    else:  
      T[i][j]=T[i][j-1]+Dist(i+1+d*j,i+1+d*(j+1))
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  x=l%d
  if r==x:
    print(0)
  elif l==x and x!=0:
    print(T[x-1][(r-x)//d-1])
  elif l==x and x==0:
    print(T[x-1][(r-x)//d-2])
  else:
    ll=(l-x)//d-1
    rr=(r-x)//d-1
    if x==0:
      ll-=1
      rr-=1
    print(T[x-1][rr]-T[x-1][ll])

Buggy python submission (verdict: Time Limit Exceeded):
h,w,d=map(int,input().split())
D=dict()
for i in range(h):
  A=[int(i) for i in input().split()]
  for j in range(w):
    D[A[j]]=[i+1,j+1]
def Dist(x,y):
  return abs(D[x][0]-D[y][0])+abs(D[x][1]-D[y][1])
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  ans=0
  rep=(r-l)//d
  for j in range(rep):
    ans+=Dist(l+j*d,l+(j+1)*d)
  print(ans)

Fixed submission:
h,w,d=map(int,input().split())
D=dict()
for i in range(h):
  A=[int(i) for i in input().split()]
  for j in range(w):
    D[A[j]]=[i+1,j+1]
def Dist(x,y):
  return abs(D[x][0]-D[y][0])+abs(D[x][1]-D[y][1])
T=[[0 for _ in range((h*w)//d)] for _ in range(d)]
for i in range(d):
  for j in range((h*w)//d):
    if i+1+d*(j+1)>h*w:
      continue
    elif j==0:
      T[i][j]=Dist(i+1,i+1+d)
    else:  
      T[i][j]=T[i][j-1]+Dist(i+1+d*j,i+1+d*(j+1))
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  x=l%d
  if r==x:
    print(0)
  elif l==x and x!=0:
    print(T[x-1][(r-x)//d-1])
  elif l==x and x==0:
    print(T[x-1][(r-x)//d-2])
  else:
    ll=(l-x)//d-1
    rr=(r-x)//d-1
    if x==0:
      ll-=1
      rr-=1
    print(T[x-1][rr]-T[x-1][ll])