Problem:
 Score : 400 points    Problem Statement We have a grid with H rows and W columns. The square at the i -th row and the j -th column will be called Square (i,j) .  The integers from 1 through H×W are written throughout the grid, and the integer written in Square (i,j) is A_{i,j} .  You, a magical girl, can teleport a piece placed on Square (i,j) to Square (x,y) by consuming |x-i|+|y-j| magic points.  You now have to take Q practical tests of your ability as a magical girl.  The i -th test will be conducted as follows:    Initially, a piece is placed on the square where the integer L_i is written.    Let x be the integer written in the square occupied by the piece. Repeatedly move the piece to the square where the integer x+D is written, as long as x is not R_i . The test ends when x=R_i .    Here, it is guaranteed that R_i-L_i is a multiple of D .    For each test, find the sum of magic points consumed during that test.      Constraints  1 \leq H,W \leq 300  1 \leq D \leq H×W  1 \leq A_{i,j} \leq H×W  A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))  1 \leq Q \leq 10^5  1 \leq L_i \leq R_i \leq H×W  (R_i-L_i) is a multiple of D .         Input Input is given from Standard Input in the following format:  H  W  D  A_{1,1}  A_{1,2}  ...  A_{1,W}  :  A_{H,1}  A_{H,2}  ...  A_{H,W}  Q  L_1  R_1  :  L_Q  R_Q       Output For each test, print the sum of magic points consumed during that test.  Output should be in the order the tests are conducted.        Sample Input 1 3 3 2
1 4 3
2 5 7
8 9 6
1
4 8      Sample Output 1 5    4 is written in Square (1,2) .    6 is written in Square (3,3) .    8 is written in Square (3,1) .    Thus, the sum of magic points consumed during the first test is (|3-1|+|3-2|)+(|3-3|+|1-3|)=5 .       Sample Input 2 4 2 3
3 7
1 4
5 2
6 8
2
2 2
2 2      Sample Output 2 0
0  Note that there may be a test where the piece is not moved at all, and there may be multiple identical tests.       Sample Input 3 5 5 4
13 25 7 15 17
16 22 20 2 9
14 11 12 1 19
10 6 23 8 18
3 21 5 24 4
3
13 13
2 10
13 13      Sample Output 3 0
5
0

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    read = sys.stdin.read
    H, W, D = (int(i) for i in input().split())
    R = [r for r in read().rstrip().split('\n')]
    A = [[int(i) for i in r.split()] for r in R[:H]]

    B = [0]*(H*W+1)
    pos = {A[i][j]: (i+1, j+1) for i in range(H) for j in range(W)}

    for i in range(D+1, H*W+1):
        y, x = pos[i - D]
        ny, nx = pos[i]
        power = abs(nx - x) + abs(ny - y)
        B[i] = B[i - D] + power

    for r in R[H+1:]:
        le, ri = (int(i) for i in r.split())
        print(B[ri] - B[le])


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]
    Q = int(input())
    LR = [[int(i) for i in input().split()] for j in range(Q)]

    B = [0]*(H*W+1)
    pos = {A[i][j]: (i+1, j+1) for i in range(H) for j in range(W)}

    for i in range(D+1, H*W+1):
        y, x = pos[i - D]
        ny, nx = pos[i]
        power = abs(nx - x) + abs(ny - y)
        B[i] = B[i - D] + power

    for le, ri in LR:
        print(B[ri] - B[le])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline

h, w, d = [int(x) for x in input().split()]
n = h*w
a = [[int(x) for x in input().split()] for _ in range(h)]
q = int(input())
lr = [[int(x) for x in input().split()] for _ in range(q)]

from collections import defaultdict
b = defaultdict(list)
for i in range(h):
    for j in range(w):
        b[a[i][j] - 1] = [i, j]
dist = [float('inf')]*n
for i in range(d):
    dist[i] = 0
    while i + d < n:
        x1, y1 = b[i]
        x2, y2 = b[i + d]
        dist[i + d] = dist[i] + abs(x1 - x2) + abs(y1 - y2)
        i += d
for i in range(q):
    l, r = lr[i]
    l -= 1
    r -= 1
    print(dist[r] - dist[l])

Solution (Python):
H, W, D = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
x = [0]*(H*W+D+1)
y = [0]*(H*W+D+1)
for k in range(W):
    for l in range(H):
        x[A[l][k]] = k+1
        y[A[l][k]] = l+1

d = [0]*(H*W+D+1)
for k in range(H*W,0,-1):
    d[k] = d[k+D] + abs(x[k]-x[k+D]) + abs(y[k]-y[k+D])

for _ in range(int(input())):
    L, R = map(int,input().split())
    print(d[L]-d[R])

Solution (Python):


import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))

def resolve():
    H,W,D=pin()
    precal_magicalresource=[]
    places_num=[None]*(H*W+1)
    for h in range(1,H+1):
        temp=tupin()
        for w in range(1,W+1):
            places_num[temp[w-1]]=(h,w)
    places_num[0]=(0,0)
    

    for d in range(D):
        d_mag=[]
        d_mag.append(0)
        temp=places_num[d]
        p=0
        while(1):
            d+=D
            if d>H*W:break
        
            s=abs(temp[0]-places_num[d][0])
            t=abs(temp[1]-places_num[d][1])
            p+=s+t
            d_mag.append((p))
            temp=places_num[d]
        precal_magicalresource.append(d_mag)
        
    Q=int(input())    
    for q in range(Q):
        l,r=pin()
        lm=l%D
        rd=r//D
        ld=l//D
        print(precal_magicalresource[lm][rd]-precal_magicalresource[lm][ld])

resolve()

Solution (Python):
h,w,d = tuple(map(int,input().split()))

a = [[int(t)for t in input().split()]for _ in [0]*h]

pos = [0]*(h*w)

for i in range(h):
  for j in range(w):
    pos[a[i][j]-1] = (i,j)

cusum = [0]*d


for i in range(h*w-d):
  x,y = pos[i]
  z,w = pos[i+d]
  cost = abs(x-z)+abs(y-w)
  cusum.append(cusum[-d]+cost)

q = int(input())

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

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    H, W, D = (int(i) for i in input().split())
    A = [[int(i) for i in input().split()] for j in range(H)]
    Q = int(input())
    LR = [[int(i) for i in input().split()] for j in range(Q)]
    B = [10**9]*(H*W+1)
    pos = {A[i][j]: (i+1, j+1) for i in range(H) for j in range(W)}
    for i in range(1, H*W+1):
        cur_p = i
        if B[cur_p] < 10**9:
            continue
        B[cur_p] = 0
        y, x = pos[cur_p]
        while cur_p + D <= H*W:
            np = cur_p + D
            ny, nx = pos[np]
            power = abs(nx - x) + abs(ny - y)
            B[np] = B[cur_p] + power
            cur_p = np
            y, x = ny, nx

    for le, ri in LR:
        print(B[ri] - B[le])


if __name__ == '__main__':
    main()

Solution (Python):
H,W,D = map(int,input().split())

A = []
for _ in range(H):
    A.append(list(map(int,input().split())))

M = [[0 for _ in range(W)] for i in range(H)]

num = [[] for _ in range(H*W+1)]
for i in range(H):
    for j in range(W):
        num[A[i][j]].append([i,j])

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

for i in range(D,H*W+1):
    if i <= D:
        continue
    else:
        dist[i] = dist[i-D] + abs(num[i][0][0]-num[i-D][0][0]) + abs(num[i][0][1]-num[i-D][0][1])


Q = int(input())

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

Solution (Python):
h, w, d = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(h)]

B = [0]*(h*w)

C = [0]*(h*w)

for i in range(h):
    for j in range(w):
        a = A[i][j]
        B[a-1] = (j+1, i+1)

for i in range(h*w):
    if i-d >= 0:
        j = i-d
        px, py = B[j]
        x, y = B[i]
        C[i] = abs(x-px)+abs(y-py)+C[j]
    else:
        C[i] = 0


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

Solution (Python):
import sys
input = sys.stdin.readline
from collections import *

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
x, y = defaultdict(int), defaultdict(int)

for i in range(H):
    for j in range(W):
        x[A[i][j]] = i
        y[A[i][j]] = j

x[0] = x[D]
y[0] = y[D]
acc = [[0] for _ in range(D)]

for i in range(D):
    now = i
    
    while now+D<=H*W:
        acc[i].append(acc[i][-1]+abs(x[now+D]-x[now])+abs(y[now+D]-y[now]))
        now += D

Q = int(input())

for _ in range(Q):
    L, R = map(int, input().split())
    print(acc[L%D][R//D]-acc[L%D][L//D])

Solution (Python):
h,w,d=map(int,input().split())
b=[(0--(h*w-i)//d)*[0]for i in range(d)]
a=[list(map(int,input().split()))for _ in range(h)]
for i in range(h):
  for j in range(w):
    a[i][j]-=1
    b[a[i][j]%d][a[i][j]//d]=(i,j)
bb=[[0]for _ in range(d)]
for i in range(d):
  for j in range(1,len(b[i])):
    bb[i].append(bb[i][-1]+(abs(b[i][j-1][0]-b[i][j][0])+abs(b[i][j-1][1]-b[i][j][1])))
for ll,rr in [list(map(int,input().split()))for _ in range(int(input()))]:
  l=ll-1
  r=rr-1
  print(bb[l%d][r//d]-bb[l%d][l//d])

Solution (Python):
import itertools
h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
p = [0] * (h * w)
for i, j in itertools.product(range(h), range(w)):
  p[a[i][j] - 1] = (i, j)
s = [0] * d
for i in range(h * w - d):
  s.append(s[-d] + abs(p[i][0] - p[i+d][0]) + abs(p[i][1] - p[i+d][1]))
q = int(input())
for i in range(q):
  l, r = map(int, input().split())
  l -= 1
  r -= 1
  print(s[r] - s[l])

Solution (Python):
import itertools
h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
p = [0] * (h * w)
for i, j in itertools.product(range(h), range(w)):
  p[a[i][j] - 1] = (i, j)
s = [0] * d
for i in range(h * w - d):
  s.append(s[-d] + abs(p[i][0] - p[i+d][0]) + abs(p[i][1] - p[i+d][1]))
q = int(input())
for i in range(q):
  l, r = map(int, input().split())
  l -= 1
  r -= 1
  print(s[r] - s[l])

Solution (Python):
H, W, D = map(int, input().split())
A_where = [0] * (H*W+1)
A_where[0] = (-1, -1)
for p in range(H):
    A = list(map(int, input().split()))
    for q in range(W):
        A_where[A[q]] = (p, q)

Q = int(input())

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

for i in range(D+1, H*W+1):
    y1, x1 = A_where[i]
    y2, x2 = A_where[i-D]

    DP[i] = DP[i-D] + abs(y1-y2) + abs(x1-x2)

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

Solution (Python):
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]

d = {}
for y in range(H):
    for x in range(W):
        d[A[y][x]] = (y, x)

t = [[0] * (H * W // D + 1) for _ in range(D)]
for i in range(D):
    ti = t[i]
    j = 0
    if i == 0:
        j = 1
    while i + (j + 1) * D <= H * W:
        y1, x1 = d[i + j * D]
        y2, x2 = d[i + (j + 1) * D]
        ti[j + 1] = abs(y1 - y2) + abs(x1 - x2)
        j += 1
    for j in range(H * W // D):
        ti[j + 1] += ti[j]

Q = int(input())
result = []
for _ in range(Q):
    L, R = map(int, input().split())
    i = L % D
    result.append(t[i][(R - i) // D] - t[i][(L - i) // D])
print('\n'.join(str(i) for i in result))

Solution (Python):
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]

d = {}
for y in range(H):
    for x in range(W):
        d[A[y][x]] = (y, x)

t = [[0] * (H * W // D + 1) for _ in range(D)]
for i in range(D):
    j = 0
    if i == 0:
        j = 1
    while i + (j + 1) * D <= H * W:
        y1, x1 = d[i + j * D]
        y2, x2 = d[i + (j + 1) * D]
        t[i][j + 1] = abs(y1 - y2) + abs(x1 - x2)
        j += 1
    for j in range(H * W // D):
        t[i][j + 1] += t[i][j]

Q = int(input())
result = []
for _ in range(Q):
    L, R = map(int, input().split())
    i = L % D
    result.append(t[i][(R - i) // D] - t[i][(L - i) // D])
print('\n'.join(str(i) for i in result))

Solution (Python):
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]

d = {}
for y in range(H):
    for x in range(W):
        d[A[y][x]] = (y, x)

t = [[0] * (H * W // D + 1) for _ in range(D)]
for i in range(D):
    j = 0
    if i == 0:
        j = 1
    while i + (j + 1) * D <= H * W:
        y1, x1 = d[i + j * D]
        y2, x2 = d[i + (j + 1) * D]
        t[i][j + 1] = abs(y1 - y2) + abs(x1 - x2)
        j += 1
    for j in range(H * W // D):
        t[i][j + 1] += t[i][j]

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    i = L % D
    print(t[i][(R - i) // D] - t[i][(L - i) // D])

Solution (Python):
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]

d = {}
for y in range(H):
    Ay = A[y]
    for x in range(W):
        d[Ay[x]] = (y, x)

t = [[0] * (H * W // D + 1) for _ in range(D)]
for i in range(D):
    ti = t[i]
    j = 0
    if i == 0:
        j = 1
    while i + (j + 1) * D <= H * W:
        y1, x1 = d[i + j * D]
        y2, x2 = d[i + (j + 1) * D]
        ti[j + 1] = abs(y1 - y2) + abs(x1 - x2)
        j += 1
    for j in range(len(ti) - 1):
        ti[j + 1] += ti[j]

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    i = L % D
    print(t[i][(R - i) // D] - t[i][(L - i) // D])

Solution (Python):
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]

d = {}
for y in range(H):
    Ay = A[y]
    for x in range(W):
        d[Ay[x]] = (y, x)

t = [[0] * ((H * W + D - 1) // D + 1) for _ in range(D)]
for i in range(D):
    ti = t[i]
    j = 0
    if i == 0:
        j = 1
    while i + (j + 1) * D <= H * W:
        y1, x1 = d[i + j * D]
        y2, x2 = d[i + (j + 1) * D]
        ti[j + 1] = abs(y1 - y2) + abs(x1 - x2)
        j += 1
    for j in range(len(ti) - 1):
        ti[j + 1] += ti[j]

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    i = L % D
    print(t[i][(R - i) // D] - t[i][(L - i) // D])

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    H,W,D=map(int,input().split())
    A=[() for _ in range(H*W)]
    for i in range(H):
        a=list(map(int1,input().split()))
        for j,x in enumerate(a):
            A[x]=(i,j)
    c=[[0] for _ in range(D)]
    for i in range(D):
        for k,j in enumerate(range(i,H*W-D,D)):
            c[i].append(c[i][k]+abs(A[j][0]-A[j+D][0])+abs(A[j][1]-A[j+D][1]))
    Q=int(input())
    for _ in range(Q):
        L,R=map(int1,input().split())
        print(c[L%D][R//D]-c[L%D][L//D])

if __name__ == '__main__':
    main()

Solution (Python):
h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]

x = [[-1] for _ in range(h*w+d+1)]
m = []
for i in range(h):
    for j in range(w):
        x[a[i][j]] = [i, j]
        m.append([a[i][j], i, j])
m.sort()
visit = [[-1 for _i in range(w)] for _j in range(h)]

for pos, xx, yy in m:
    if visit[xx][yy] < 0:
        visit[xx][yy] = 0
        while x[pos+d][0] >= 0:
            g, h = x[pos+d]
            visit[g][h] = visit[xx][yy] + abs(g-xx)+abs(h-yy)
            xx = g
            yy = h
            pos = a[xx][yy]
for l, r in lr:
    print(visit[x[r][0]][x[r][1]]-visit[x[l][0]][x[l][1]])

Solution (Python):
h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]

x = [[-1] for _ in range(h*w+d+1)]
m = []
for i in range(h):
    for j in range(w):
        x[a[i][j]] = [i, j]
        m.append([a[i][j], i, j])
m.sort()
visit = [[-1 for _i in range(w)] for _j in range(h)]

for pos, xx, yy in m:
    if visit[xx][yy] < 0:
        visit[xx][yy] = 0
        while x[pos+d][0] >= 0:
            g, h = x[pos+d]
            visit[g][h] = visit[xx][yy] + abs(g-xx)+abs(h-yy)
            xx = g
            yy = h
            pos = a[xx][yy]
for l, r in lr:
    print(visit[x[r][0]][x[r][1]]-visit[x[l][0]][x[l][1]])

Solution (Python):
from collections import defaultdict

H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for _ in range(H)]
M=defaultdict(list)
for h in range(H):
    for w in range(W):
        M[A[h][w]]=[h,w]

P=defaultdict(list)
for d in range(1,D+1):
    a=d
    while a+D<=H*W:
        p=abs(M[a][0]-M[a+D][0])+abs(M[a][1]-M[a+D][1])
        if P[d]:
            P[d].append(P[d][-1]+p)
        else:
            P[d]=[0,p]
        a+=D

Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    d=L%D
    l=L//D
    r=R//D
    if d==0:
        d=D
        if len(P[d])>0:
            print(P[d][r-1]-P[d][l-1])
        else:
            print(0)
    else:
        if len(P[d])>0:
            print(P[d][r]-P[d][l])
        else:
            print(0)

Solution (Python):
H,W,D = map(int,input().split())
A = [[]]
for i in range(H):
  A.append([0]+list(map(int,input().split())))
la = [[] for o in range(H*W+1)]
for i in range(1,H+1):
  for j in range(1,W+1):
    la[A[i][j]].append(i)
    la[A[i][j]].append(j)
Q = int(input())
q = []
for i in range(Q):
  q.append(list(map(int,input().split())))

l = [[0]+[0 for i in range((H*W-j)//D)] for j in range(D)]

i = 0
v = l[i]
for j in range(1,len(l[0])-1):
  mae = i + D*j
  ato = i + D*(j+1)
  v[j+1] = v[j] + abs(la[mae][0]-la[ato][0]) + abs(la[mae][1]-la[ato][1])

for i in range(1,D):
  v = l[i]
  for j in range(len(v)-1):
    mae = i + D*j
    ato = i + D*(j+1)
    v[j+1] = v[j] + abs(la[mae][0]-la[ato][0]) + abs(la[mae][1]-la[ato][1])

for i in range(Q):
  L,R = q[i][0],q[i][1]
  amari = L%D
  haji = (L-amari)//D
  owari = (R-amari)//D  
  print(l[amari][owari]-l[amari][haji])

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
h,w,d=map(int,input().split())
pos=[0]*(h*w+1)
for i in range(h):
    a=list(map(int,input().split()))
    for j in range(w):
        pos[a[j]]=(i,j)
ans=[0]*(h*w+1)
visited=[True]*(h*w+1)
def dfs(s,nxt):
    if nxt>h*w:
        return 
    visited[s]=False
    dfs(nxt,nxt+d)
    x,y=pos[s]
    nx,ny=pos[nxt]
    ans[s]+=ans[nxt]+abs(nx-x)+abs(ny-y)
for i in range(1,h*w+1):
    if visited[i]:
        dfs(i,i+d)
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(ans[l]-ans[r])

Solution (Python):
import sys
from collections import defaultdict


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)


def main():
    H, W, D = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    M = defaultdict(list)
    for h in range(H):
        for w in range(W):
            M[A[h][w]] = [h, w]
    P = defaultdict(list)
    for d in range(1, D + 1):
        a = d
        while a <= H * W - D:
            p = abs(M[a][0] - M[a + D][0]) + abs(M[a][1] - M[a + D][1])
            if P[d]:
                P[d].append(P[d][-1] + p)
            else:
                P[d] = [0, p]
            a += D
    
    Q = int(input())
    for i in range(Q):
        L, R = map(int, input().split())
        d = L % D
        l = L // D
        r = R // D
        if d == 0:
            d = D
            if len(P[d]) > 0:
                print(P[d][r - 1] - P[d][l - 1])
            else:
                print(0)
        else:
            if len(P[d])>0:
                print(P[d][r] - P[d][l])
            else:
                print(0)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    H, W, D = map(int, input().split())
    A = []
    for _ in range(H):
        a = list(map(int, input().split()))
        A.append(a)

    place = {}
    for h in range(H):
        for w in range(W):
            place[A[h][w]] = (h, w)

    diff = dict()
    for d in range(1, D + 1):
        cumsum = [0]
        ds = list(range(d, H * W + 1, D))
        N = len(ds)
        for i in range(N - 1):
            x, y = place[ds[i]]
            X, Y = place[ds[i + 1]]
            tmp = cumsum[-1] + abs(x - X) + abs(y - Y)
            cumsum.append(tmp)
        diff[d % D] = cumsum

    Q = int(input())
    ans = []
    for _ in range(Q):
        L, R = map(int, input().split())
        m = L % D
        if m == 0:
            L_idx = L // D - 1
            R_idx = R // D - 1
        else:
            L_idx = L // D
            R_idx = R // D
        a = diff[m][R_idx] - diff[m][L_idx]
        ans.append(a)

    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Solution (Python):
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])

Solution (Python):
H,W,D=map(int,input().split())
G=[[]]*(H*W)
J=[0]*(H*W)
for i in range(H):
  for j,a in enumerate(list(map(int,input().split()))):
    G[a-1]=[i,j]
    
for i in range(H*W):
  if i-D>=0:
    J[i]=J[i-D]+abs(G[i][0]-G[i-D][0])+abs(G[i][1]-G[i-D][1])
      
for i in range(int(input())):
  l,r=map(int,input().split())
  print(J[r-1]-J[l-1])

Solution (Python):
H,W,D=map(int,input().split())
A=[]
for i in range(H):
    a=list(map(int,input().split()))
    A.append(a)
Q=int(input())
L=[]
R=[]

lst=[[]for _ in range(H*W)]
for i in range(H):
    for j in range(W):
        lst[A[i][j]-1].append(i)
        lst[A[i][j]-1].append(j)


d=[]
for i in range(D):
    cnt=[0]
    for j in range(i+D,H*W,D):
        cnt.append(cnt[-1]+abs(lst[j][0]-lst[j-D][0])+abs(lst[j][1]-lst[j-D][1]))
    d.append(cnt)
ans=[]


for i in range(Q):
    l,r=map(int,input().split())
    ll=(l-1)%D
    count=d[ll]
    r-=1
    l-=1
    
    vall=count[l//D]
    
    
    valr=count[r//D]
    val=valr-vall
    
    ans.append(val)

for i in range(Q):
    print(ans[i])

Solution (Python):
H, W, D = map(int, input().split())
number = [[0,0] for _ in range(H*W)]
cost = [0] * (H*W)
for i in range(H):
  a = list(map(int, input().split()))
  for j in range(W):
    number[a[j]-1] = [i, j]
for i in range(D):
  cost[i] = 0
for j in range(D, H*W):
  cost[j] = cost[j-D] + abs(number[j][0]-number[j-D][0]) + abs(number[j][1]-number[j-D][1])
Q = int(input())
for i in range(Q):
  L, R = map(int, input().split())
  print(cost[R-1] - cost[L-1])

Solution (Python):



H,W,D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [tuple(map(int, input().split())) for _ in range(Q)]

num = [None] * (H*W)
for i in range(H):
    for j in range(W):
        num[A[i][j] - 1] = (i,j)


accum = [0] * (H*W)

for i in range(D):
    j = 0
    while i + j*D <= (H*W) - 1:
        if j == 0:
            accum[i + j*D] = 0
        else:
            curr = i + j*D
            prev = i + (j-1)*D
            accum[curr] = accum[prev] + abs(num[prev][0] - num[curr][0]) + abs(num[prev][1] - num[curr][1])

        j += 1

for l,r in LR:
    print(accum[r-1] - accum[l-1])

Solution (Python):
H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
dic={}
for i in range(H):
    for j in range(W):
        dic[A[i][j]]=(i,j)
dist=[0]*(H*W+10)
for i in range(D+1,H*W+1):
    xd=abs(dic[i][0]-dic[i-D][0])
    yd=abs(dic[i][1]-dic[i-D][1])
    dist[i]=dist[i-D]+xd+yd
Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    print(dist[R]-dist[L])

Solution (Python):
h,w,d=map(int,input().split())
A=[]
for _ in range(h):
    A.append([int(i) for i in input().split()])
q=int(input())
lr=[]
for _ in range(q):
    l,r = map(int,input().split())
    lr.append((l,r))
D=dict()
for i in range(h):
    for j in range(w):
        D[A[i][j]]=(i,j)

def dist(a,b):
    return abs(a[0]-b[0])+abs(a[1]-b[1])

res=dict()
for i in range(d):
    j=i+1
    cnt=0
    res[j]=0
    
    while j<=h*w-d:
        
        res[j+d] = res[j]+dist(D[j],D[j+d]) 
        j+=d
        cnt+=1
for l,r in lr:
    print(res[r]-res[l])

Solution (Python):
H, W, D = map(int,input().split())
A = []
L = [None for _ in range(H * W)]
for _ in range(H):
    A.append(list(map(int,input().split())))
for i in range(H):
    for j in range(W):
        L[A[i][j]-1] = [i, j]
Q = int(input())
cnt = [[0] for _ in range(D)]
for i in range(D):
    j = i
    while j + D <= H * W - 1:
        cnt[i].append(cnt[i][-1] + abs(L[j + D][0] - L[j][0]) + abs(L[j + D][1] - L[j][1]))
        j += D
for _ in range(Q):
    L, R = map(int,input().split())
    i = (L - 1) % D
    print(cnt[i][(R-1)//D] - cnt[i][(L-1)//D])

Solution (Python):



H,W,D = map(int,input().split())
MAX = H*W
A = [list(map(int,input().split())) for i in range(H)]
Point = [0]*(MAX+1)
for h in range(H):
    for w in range(W):
        Point[A[h][w]] = (h,w)
K = []
for i in range(1,D+1):
    List = []
    n = i
    h,w = Point[n]
    cost = 0
    while n<=MAX:
        y,x = Point[n]
        cost += abs(h-y)+abs(w-x)
        List.append(cost)
        h,w = y,x
        n+=D
    K.append(List)
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    a,l,r = (L-1)%D,(L-1)//D,(R-1)//D
    print(K[a][r]-K[a][l])

Solution (Python):
h, w, d = map(int, input().split())
a = []
for i in range(h):
    a.append(list(map(int, input().split())))
dic=dict()
for i in range(h):
    for j in range(w):
        dic[a[i][j]] = (i, j)
co_order = [None] + [value for key, value in sorted(dic.items(), key=lambda x: x[0])]
cost = {i: [0] for i in range(1, d + 1)}

for i in range(1, d + 1):
    sx, sy= co_order[i]
    for ex, ey in co_order[i+d::d]:
        cost[i].append(cost[i][-1] + abs(sx - ex) + abs(sy - ey))
        sx, sy = ex, ey
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    index = (r-1)%d+1
    print(cost[index][(r-1)//d] - cost[index][(l-1)//d])

Solution (Python):
h,w,d = map(int,input().split())
li = [-1]*h*w

for i in range(h):
    a = list(map(int,input().split()))
    for j in range(w):
        li[a[j]-1] = (i,j)

li2 = [[] for _ in range(d)]
li3 = [[0] for _ in range(d)]
for i in range(d):
    li_tmp = li[i::d]
    for j in range(len(li_tmp)-1):
        li2[i].append(abs(li_tmp[j][0]-li_tmp[j+1][0]) + abs(li_tmp[j][1]-li_tmp[j+1][1]))

for i in range(d):
    for j in range(len(li2[i])):
        if j == 0:
            li3[i].append(li2[i][j])
        else:
            li3[i].append(li3[i][-1] + li2[i][j])

q = int(input())
for _ in range(q):
    l,r = map(int,input().split())
    l -= 1
    r -= 1
    l1 = l % d
    print(li3[l1][r//d] - li3[l1][l//d])

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
_LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

H,W,D = LI()
A = [_LI() for _ in range(H)]
Q = NI()
LR = [_LI() for _ in range(Q)]

dist =  [[0 for _ in range(math.ceil(H*W/D))] for _ in range(D)]
S  = []
for i in range(H):
    for j in range(W):
        S.append((A[i][j],i,j))
S.sort()

for a,i,j in S[D:]:
    dist[a%D][a//D] = dist[a%D][a//D-1] + abs(S[a-D][1]-i) + abs(S[a-D][2]-j)

for l,r in LR:
    ans = dist[r%D][r//D] - dist[l%D][l//D]
    print(ans)

Solution (Python):
h,w,d=map(int,input().split())
a=[ [ [] for j in range(int(h*w/d+1)) ] for i in range(d) ]
a1=[ [ [] for j in range(int(h*w/d+1)) ] for i in range(d) ]
for i in range(h):
  i+=1
  tmp=list(map(int,input().split()))
  for j in range(w):
    num=tmp[j]
    j+=1
    a[num%d][int( (num-1)/d)]=[i,j]
for i in range(len(a)):
  a1[i][0]=0
  for j in range(len(a[i])-1):
    j=j+1
    if a[i][j]!=[]:
      a1[i][j]=a1[i][j-1]+abs(a[i][j][0]-a[i][j-1][0])+abs(a[i][j][1]-a[i][j-1][1])

q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  print(a1[l%d][int((r-1)/d)]-a1[l%d][int((l-1)/d)])

Solution (Python):
H, W, D = map(int, input().split())
grid = []
memo = [[] for _ in range(H*W+1)]
for i in range(H):
    grid.append(list(map(int, input().split())))
    for j in range(len(grid[i])):
        memo[grid[i][j]].append(i)
        memo[grid[i][j]].append(j)

S = [0 for i in range(H*W+1)]

for i in range(H*W+1):
    if(i <= D):
        continue
    S[i] = S[i-D]+ abs(memo[i][0]-memo[i-D][0])+abs(memo[i][1]-memo[i-D][1])

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

Solution (Python):
ma = lambda :map(int,input().split())
h,w,d = ma()
area_d = [[] for i in range(d)]
rs = [[0] for i in range(d)]
for i in range(h):
    for j,a in enumerate(ma()):
        area_d[a%d].append((a,i,j))
for i in range(d):
    area_d[i].sort()

for i in range(d):
    yp,xp = 0,0
    for a,y,x in area_d[i]:
        rs[i].append(rs[i][-1] + abs(y-yp)+abs(x-xp))
        yp,xp = y,x
q = int(input())
for i in range(q):
    l,r = ma()
    lq,lr = divmod(l,d)
    rq,rr = divmod(r,d)
    if lr==0:print(rs[lr][rq] - rs[lr][lq])
    else:print(rs[lr][rq+1] - rs[lr][lq+1])

Solution (Python):
H, W, D = map(int, input().split())
A = []
for i in range(H):
    A.append(list(map(int, input().split())))

num = [() for _ in range(H*W+1)]
for i in range(H):
    for j in range(W):
        num[A[i][j]] = (i,j)
wa = [0]*(H*W+1)
for i in range(D+1, H*W+1):
    wa[i] = wa[i-D] + abs(num[i][0]-num[i-D][0])+abs(num[i][1]-num[i-D][1])

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

Solution (Python):
H,W,D = map(int,input().split(" "))
mass = [[0 for _ in range(W)] for _ in range(H)]
num = [[0,0] for _ in range(H * W + 1)]
DP = [0 for _ in range(H * W + 1)]
for i in range(H):
  mass[i] = list(map(int,input().split(" ")))
for i in range(H):
  for i2 in range(W):
    num[mass[i][i2]] = [i,i2]
for i in range(D,W * H + 1):
  DP[i] = DP[i - D] + abs(num[i][0] - num[i - D][0]) + abs(num[i][1] - num[i - D][1])
L = 0
R = 0
ans = 0
Q = int(input())
for i in range(Q):
  ans = 0
  L,R = map(int,input().split(" "))
  print(DP[R] - DP[L])

Solution (Python):
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
X = [list(map(int, input().split())) for _ in range(Q)]

ctr = {}
for i in range(H):
    for j in range(W):
        ctr[A[i][j]] = (i, j)

memo = [0] * (H * W + 1)
for n in range(D + 1, H * W + 1):
    i, j = ctr[n - D]
    x, y = ctr[n]
    memo[n] = abs(x - i) + abs(y - j) + memo[n - D]

for l, r in X:
    print(memo[r] - memo[l])

Solution (Python):
H, W, D = map(int, input().split(" "))
coord = {}

for i in range(H):
    for j, A in enumerate(map(int, input().split(" "))):
        coord[A] = (i, j)

magic = [0 for i in range(H * W + 1)]
for i in range(H * W + 1):
    if i + D <= H * W:
        magic[i + D] += magic[i]
        if i != 0:
            magic[i + D] += abs(coord[i][0] - coord[i + D][0]) + abs(coord[i][1] - coord[i + D][1])

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split(" "))
    print(magic[R] - magic[L])