Buggy python submission (verdict: Time Limit Exceeded):
def main():
  H,W,D = map(int,input().split())
  A = [[] for _ in range(H)]
  posi = [[]] * (H * W)
  
  for _ in range(H):
    a = list(map(int,input().split()))
    A[_] = a
    for i,j in enumerate(a):
      k = i + 1
      t = _ + 1
      posi[j - 1] = [t,k]
  
  Q = int(input())
  
  acdist = [0] * (H * W)
  
  for _ in range(0,H * W - D):
    for d in range(_,H * W - D,D):
      acdist[_] += abs(posi[d + D][0] - posi[d][0]) + abs(posi[d + D][1] - posi[d][1])
  
  for i in range(Q):
    l,r = map(int,input().split())
    print(acdist[l - 1] - acdist[r - 1])
    
if __name__ == '__main__':
  main()

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

for _ in range(H):
  a = list(map(int,input().split()))
  for i,j in enumerate(a):
    posi[j - 1] = [_ + 1,i + 1]

Q = int(input())

acdist = [0] * (H * W)

for _ in range(0,H * W - D):
  acdist[_ + D] += acdist[_] + abs(posi[_ + D][0] - posi[_][0]) + abs(posi[_ + D][1] - posi[_][1])

for i in range(Q):
  l,r = map(int,input().split())
  print(acdist[r - 1] - acdist[l - 1])

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D = map(int,input().split())
A = [[] for _ in range(H)]
posi = [[]] * (H * W)

for _ in range(H):
  a = list(map(int,input().split()))
  A[_] = a
  for i,j in enumerate(a):
    k = i + 1
    t = _ + 1
    posi[j - 1] = [t,k]

Q = int(input())

dist = [0] * (H * W)
acdist = [0] * (H * W)

for _ in range(0,H * W - D):
  for d in range(_,H * W - D,D):
    acdist[_] += abs(posi[d + D][0] - posi[d][0]) + abs(posi[d + D][1] - posi[d][1])

for i in range(Q):
  l,r = map(int,input().split())
  print(acdist[l - 1] - acdist[r - 1])

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

for _ in range(H):
  a = list(map(int,input().split()))
  for i,j in enumerate(a):
    posi[j - 1] = [_ + 1,i + 1]

Q = int(input())

acdist = [0] * (H * W)

for _ in range(0,H * W - D):
  acdist[_ + D] += acdist[_] + abs(posi[_ + D][0] - posi[_][0]) + abs(posi[_ + D][1] - posi[_][1])

for i in range(Q):
  l,r = map(int,input().split())
  print(acdist[r - 1] - acdist[l - 1])

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D = map(int,input().split())
A = [[] for _ in range(H)]
posi = [[]] * (H * W)

for _ in range(H):
  a = list(map(int,input().split()))
  A[_] = a
  for i,j in enumerate(a):
    k = i + 1
    t = _ + 1
    posi[j - 1] = [t,k]

Q = int(input())

dist = [0] * (H * W)
acdist = [0] * (H * W)

for _ in range(0,H * W - D):
  dist[_] = abs(posi[_ + D][0] - posi[_][0]) + abs(posi[_ + D][1] - posi[_][1])

for d in range(0,H * W - D):
   acdist[d] = sum([dist[i] for i in range(d,H * W,D)])

for i in range(Q):
  l,r = map(int,input().split())
  print(acdist[l - 1] - acdist[r - 1])

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

for _ in range(H):
  a = list(map(int,input().split()))
  for i,j in enumerate(a):
    posi[j - 1] = [_ + 1,i + 1]

Q = int(input())

acdist = [0] * (H * W)

for _ in range(0,H * W - D):
  acdist[_ + D] += acdist[_] + abs(posi[_ + D][0] - posi[_][0]) + abs(posi[_ + D][1] - posi[_][1])

for i in range(Q):
  l,r = map(int,input().split())
  print(acdist[r - 1] - acdist[l - 1])

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D = map(int,input().split())
A = [[] for _ in range(H)]
posi = [[]] * (H * W)

for _ in range(H):
  a = list(map(int,input().split()))
  A[_] = a
  for i,j in enumerate(a):
    k = i + 1
    t = _ + 1
    posi[j - 1] = [t,k]


Q = int(input())

for i in range(Q):
  ans = 0
  l,r = map(int,input().split())
  power = 0
  for j in range(l - 1,r - D,D):
    ans += abs(posi[j + D][0] - posi[j][0]) + abs(posi[j + D][1] - posi[j][1])
  print(ans)

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

for _ in range(H):
  a = list(map(int,input().split()))
  for i,j in enumerate(a):
    posi[j - 1] = [_ + 1,i + 1]

Q = int(input())

acdist = [0] * (H * W)

for _ in range(0,H * W - D):
  acdist[_ + D] += acdist[_] + abs(posi[_ + D][0] - posi[_][0]) + abs(posi[_ + D][1] - posi[_][1])

for i in range(Q):
  l,r = map(int,input().split())
  print(acdist[r - 1] - acdist[l - 1])