Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=map(int,input().split())
position=[None]*(H*W+1)
for i in range(H):
  A=list(map(int,input().split()))
  for j in range(len(A)):
    position[A[j]]=[i,j]

dp=[0]*(H*W+1)

for i in range(1,len(dp)):
  if i+D>=len(dp):
    continue
  dp[i]=abs(position[i+D][0]-position[i][0])+abs(position[i+D][1]-position[i][1])

dpsum=[[0 for i in range(H*W+1)] for j in range(D)]

for i in range(1,len(dp)):
  if i-D>=0:
    dpsum[i%D][i]=dpsum[i%D][i-D]+dp[i]
  else:
    dpsum[i%D][i]=dp[i]

Q=int(input())
for i in range(Q):
  L,R=map(int,input().split())
  if L==R:
    print(0)
  elif L-D>0:
    print(dpsum[R%D][R-D]-dpsum[L%D][L-D])
  else:
    print(dpsum[R%D][R-D])


Fixed submission:
H,W,D=map(int,input().split())
position=[None]*(H*W+1)
for i in range(H):
  A=list(map(int,input().split()))
  for j in range(len(A)):
    position[A[j]]=[i,j]

dp=[0]*(H*W+1)

for i in range(1,len(dp)):
  if i+D>=len(dp):
    continue
  dp[i]=abs(position[i+D][0]-position[i][0])+abs(position[i+D][1]-position[i][1])

dpsum=[0]*(H*W+1)

for i in range(1,len(dp)):
  if i-D>=0:
    dpsum[i]=dpsum[i-D]+dp[i]
  else:
    dpsum[i]=dp[i]

Q=int(input())
for i in range(Q):
  L,R=map(int,input().split())
  if L==R:
    print(0)
  elif L-D>0:
    print(dpsum[R-D]-dpsum[L-D])
  else:
    print(dpsum[R-D])

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=map(int,input().split())
position=[None]*(H*W+1)
for i in range(H):
  A=list(map(int,input().split()))
  for j in range(len(A)):
    position[A[j]]=[i,j]

dp=[0]*(H*W+1)

for i in range(1,len(dp)):
  if i+D>=len(dp):
    continue
  dp[i]=abs(position[i+D][0]-position[i][0])+abs(position[i+D][1]-position[i][1])

dpsum=[[0 for i in range(H*W+1)] for j in range(D)]

for i in range(1,len(dp)):
  if i-D>=0:
    dpsum[i%D][i]=dpsum[i%D][i-D]+dp[i]
  else:
    dpsum[i%D][i]=dp[i]

Q=int(input())
for i in range(Q):
  L,R=map(int,input().split())
  if L==R:
    print(0)
  elif L-D>0:
    print(dpsum[R%D][R-D]-dpsum[L%D][L-D])
  else:
    print(dpsum[R%D][R-D])


Fixed submission:
H,W,D=map(int,input().split())
position=[None]*(H*W+1)
for i in range(H):
  A=list(map(int,input().split()))
  for j in range(len(A)):
    position[A[j]]=[i,j]

dp=[0]*(H*W+1)

for i in range(1,len(dp)):
  if i+D>=len(dp):
    continue
  dp[i]=abs(position[i+D][0]-position[i][0])+abs(position[i+D][1]-position[i][1])

dpsum=[0]*(H*W+1)

for i in range(1,len(dp)):
  if i-D>=0:
    dpsum[i]=dpsum[i-D]+dp[i]
  else:
    dpsum[i]=dp[i]

Q=int(input())
for i in range(Q):
  L,R=map(int,input().split())
  if L==R:
    print(0)
  elif L-D>0:
    print(dpsum[R-D]-dpsum[L-D])
  else:
    print(dpsum[R-D])

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=map(int,input().split())
position=[None]*(H*W+1)
for i in range(H):
  A=list(map(int,input().split()))
  for j in range(len(A)):
    position[A[j]]=[i,j]

dp=[0]*(H*W+1)

for i in range(1,len(dp)):
  if i+D>=len(dp):
    continue
  dp[i]=abs(position[i+D][0]-position[i][0])+abs(position[i+D][1]-position[i][1])

Q=int(input())
for i in range(Q):
  L,R=map(int,input().split())
  print(sum(dp[L:R:D]))

Fixed submission:
H,W,D=map(int,input().split())
position=[None]*(H*W+1)
for i in range(H):
  A=list(map(int,input().split()))
  for j in range(len(A)):
    position[A[j]]=[i,j]

dp=[0]*(H*W+1)

for i in range(1,len(dp)):
  if i+D>=len(dp):
    continue
  dp[i]=abs(position[i+D][0]-position[i][0])+abs(position[i+D][1]-position[i][1])

dpsum=[0]*(H*W+1)

for i in range(1,len(dp)):
  if i-D>=0:
    dpsum[i]=dpsum[i-D]+dp[i]
  else:
    dpsum[i]=dp[i]

Q=int(input())
for i in range(Q):
  L,R=map(int,input().split())
  if L==R:
    print(0)
  elif L-D>0:
    print(dpsum[R-D]-dpsum[L-D])
  else:
    print(dpsum[R-D])