Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[[0]*(H*W+1) for _ in range(H*W+1)];f=0
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
if f:
  for i in range(1,D+1):
    for j in range(1,H*W//D+1):
      if i+D*j<=H*W:g[i][i+j*D]=abs(d[i+j*D-D][0]-d[i+j*D][0])+abs(d[i+j*D-D][1]-d[i+j*D][1])+g[i][i+D*j-D]
  g[0]=g[D]
else:
  for i in range(1,H*W-D+1):
    g[i][i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])
for _ in range(Q):
  l,r=map(int,input().split());t=l%D;a=0
  if f:print(g[t][r]-g[t][l])
  else:
    while l<r:
      a+=g[l][l+D];l+=D
    print(a)

Fixed submission:
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[0]*(H*W+1)
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,H*W-D+1):
  g[i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])+g[i]
for q in range(Q):
  l,r=map(int,input().split());print(g[r]-g[l])

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[[0]*(H*W+1) for _ in range(H*W+1)];f=1
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
if f:
  for i in range(1,D+1):
    for j in range(1,H*W//D+1):
      if i+D*j<=H*W:g[i][i+j*D]=abs(d[i+j*D-D][0]-d[i+j*D][0])+abs(d[i+j*D-D][1]-d[i+j*D][1])+g[i][i+D*j-D]
  g[0]=g[D]
else:
  for i in range(1,H*W-D+1):
    g[i][i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])
for _ in range(Q):
  l,r=map(int,input().split());t=l%D;a=0
  if f:print(g[t][r]-g[t][l])
  else:
    while l<r:
      a+=g[l][l+D];l+=D
    print(a)

Fixed submission:
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[0]*(H*W+1)
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,H*W-D+1):
  g[i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])+g[i]
for q in range(Q):
  l,r=map(int,input().split());print(g[r]-g[l])

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[[0]*(H*W+1) for _ in range(H*W+1)];f=D<H*W
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
if f:
  for i in range(1,D+1):
    for j in range(1,H*W//D+1):
      if i+D*j<=H*W:g[i][i+j*D]=abs(d[i+j*D-D][0]-d[i+j*D][0])+abs(d[i+j*D-D][1]-d[i+j*D][1])+g[i][i+D*j-D]
  g[0]=g[D]
else:
  for i in range(1,H*W-D+1):
    g[i][i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])
for _ in range(Q):
  l,r=map(int,input().split());t=l%D;a=0
  if f:print(g[t][r]-g[t][l])
  else:
    while l<r:
      a+=g[l][l+D];l+=D
    print(a)

Fixed submission:
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[0]*(H*W+1)
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,H*W-D+1):
  g[i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])+g[i]
for q in range(Q):
  l,r=map(int,input().split());print(g[r]-g[l])

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[[0]*(H*W+1) for _ in range(H*W+1)];f=D**2<H*W
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
if f:
  for i in range(1,D+1):
    for j in range(1,H*W//D+1):
      if i+D*j<=H*W:g[i][i+j*D]=abs(d[i+j*D-D][0]-d[i+j*D][0])+abs(d[i+j*D-D][1]-d[i+j*D][1])+g[i][i+D*j-D]
  g[0]=g[D]
else:
  for i in range(1,H*W-D+1):
    g[i][i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])
for _ in range(Q):
  l,r=map(int,input().split());t=l%D;a=0
  if f:print(g[t][r]-g[t][l])
  else:
    while l<r:
      a+=g[l][l+D];l+=D
    print(a)

Fixed submission:
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[0]*(H*W+1)
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,H*W-D+1):
  g[i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])+g[i]
for q in range(Q):
  l,r=map(int,input().split());print(g[r]-g[l])

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[[0]*(H*W+1) for _ in range(H*W+1)];f=D<100
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
if f:
  for i in range(1,D+1):
    for j in range(1,H*W//D+1):
      if i+D*j<=H*W:g[i][i+j*D]=abs(d[i+j*D-D][0]-d[i+j*D][0])+abs(d[i+j*D-D][1]-d[i+j*D][1])+g[i][i+D*j-D]
  g[0]=g[D]
else:
  for i in range(1,H*W-D+1):
    g[i][i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])
for _ in range(Q):
  l,r=map(int,input().split());t=l%D;a=0
  if f:print(g[t][r]-g[t][l])
  else:
    while l<r:
      a+=g[l][l+D];l+=D
    print(a)

Fixed submission:
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[0]*(H*W+1)
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,H*W-D+1):
  g[i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])+g[i]
for q in range(Q):
  l,r=map(int,input().split());print(g[r]-g[l])

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[[0]*(H*W+1) for _ in range(D+1)]
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,D+1):
  for j in range(1,H*W//D+1):
    if i+D*j<=H*W:g[i][i+j*D]=abs(d[i+j*D-D][0]-d[i+j*D][0])+abs(d[i+j*D-D][1]-d[i+j*D][1])+g[i][i+D*j-D]
g[0]=g[D]
for q in range(Q):
  l,r=map(int,input().split());t=l%D;print(g[t][r]-g[t][l])

Fixed submission:
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[0]*(H*W+1)
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,H*W-D+1):
  g[i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])+g[i]
for q in range(Q):
  l,r=map(int,input().split());print(g[r]-g[l])

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[[0]*(H*W+1) for _ in range(D+1)]
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,D+1):
  for j in range(1,H*W//D+1):
    if i+D*j<=H*W:g[i][i+j*D]=abs(d[i+j*D-D][0]-d[i+j*D][0])+abs(d[i+j*D-D][1]-d[i+j*D][1])+g[i][i+D*j-D]
g[0]=g[D]
for q in range(Q):
  l,r=map(int,input().split());t=l%D;print(g[t][r]-g[t][l])

Fixed submission:
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[0]*(H*W+1)
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,H*W-D+1):
  g[i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])+g[i]
for q in range(Q):
  l,r=map(int,input().split());print(g[r]-g[l])

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[0]*(H*W+1)
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,H*W-D+1):
  g[i]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])
for _ in range(Q):
  l,r=map(int,input().split());a=0
  while l<r:
    a+=g[l];l+=D
  print(a)

Fixed submission:
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[0]*(H*W+1)
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,H*W-D+1):
  g[i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])+g[i]
for q in range(Q):
  l,r=map(int,input().split());print(g[r]-g[l])

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[0]*(H*W+1)
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,H*W-D+1):
  g[i]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])
for _ in range(Q):
  l,r=map(int,input().split());a=0
  while l<r:
    a+=g[l];l+=D
  print(a)

Fixed submission:
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[0]*(H*W+1)
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,H*W-D+1):
  g[i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])+g[i]
for q in range(Q):
  l,r=map(int,input().split());print(g[r]-g[l])

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[[0]*(H*W+1) for _ in range(H*W+1)]
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(H*W,0,-1):
  if i+D<=H*W:g[i][i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])
  for j in range(H*W//D,1,-1):
    if i+D*j<=H*W:g[i][i+D*j]=g[i+D][i+D*j]+g[i][i+D]
for q in range(Q):
  l,r=map(int,input().split());print(g[l][r])

Fixed submission:
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[0]*(H*W+1)
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,H*W-D+1):
  g[i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])+g[i]
for q in range(Q):
  l,r=map(int,input().split());print(g[r]-g[l])

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[[0]*(H*W+1) for _ in range(H*W+1)]
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(H*W,0,-1):
  if i+D<=H*W:g[i][i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])
  for j in range(H*W//D,1,-1):
    if i+D*j<=H*W:g[i][i+D*j]=g[i+D][i+D*j]+g[i][i+D]
for q in range(Q):
  l,r=map(int,input().split());print(g[l][r])

Fixed submission:
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[0]*(H*W+1)
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,H*W-D+1):
  g[i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])+g[i]
for q in range(Q):
  l,r=map(int,input().split());print(g[r]-g[l])