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):
import numpy as np
H, W, D=list(map(int,input().split(" ")))


d={}
for i in range(H):
    
    for n,k in enumerate(input().split(" ")):
        d[int(k)]=[i,n]

Q=int(input())
out=[]

cost={}

for i in range(1,D+1):
    now = i + D
    cost[i]=0
    
    while now <= H * W:
        cost[now] = cost[now - D] + abs(d[now][0] - d[now - D][0]) + abs(d[now][1] - d[now - D][1])
        now += D


out=[]
for k in range(Q):
    start,end=list(map(int,input().split(" ")))
    out.append(cost[end]-cost[start])

for i in out:
    print(int(i))

Solution (Python):
import numpy as np
H,W,D = map(int,input().split())
SUM = H*W
px = np.zeros(SUM+1)
py = np.zeros(SUM+1)
for i in range(1,H+1):
    A = list(map(int, input().split()))
    for j in range(len(A)):
        px[A[j]] = i
        py[A[j]] = j + 1

d = np.zeros(SUM+1)
for t in range(D+1,SUM+1):
    d[t] = d[t-D] + abs(px[t] - px[t-D])+ abs (py[t] - py[t-D]);
        
Q = int(input())
L = []
R = []
for i in range(Q): 
    l,r = map(int, input().split())
    print(int(d[r]-d[l]))

Solution (Python):
def d_practical_skill_test(H, W, D, A, Q, I):
    
    px = [0 for _ in range(H * W + 1)]
    py = [0 for _ in range(H * W + 1)]  
    d = [0 for _ in range(H * W + 1)]
    for i in range(H):
        for j in range(W):
            px[A[i][j]] = i
            py[A[i][j]] = j
    for i in range(D + 1, H * W + 1):
        d[i] = d[i - D] + abs(px[i] - px[i - D]) + abs(py[i] - py[i - D])
    ans = []
    for l, r in I:
        ans.append(str(d[r] - d[l]))
    return '\n'.join(ans)

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())
I = [[int(i) for i in input().split()] for j in range(Q)]
print(d_practical_skill_test(H, W, D, A, Q, I))

Solution (Python):

line = input().split(" ")
h = int(line[0])
w = int(line[1])
d = int(line[2])

table = [0 for _ in range(h*w+1)]
for hi in range(h):
    line = list(map(int, input().split(" ")))

    for wi in range(w):
        table[line[wi]] = (hi+1, wi+1)

def calc(l,r):
    ret = 0
    if l!=r:
        c1 = table[l]
        c2 = table[r]
        ret += abs(c1[0]-c2[0])+abs(c1[1]-c2[1])
    return ret

acc = [0 for _ in range(h*w+1)]
for dd in range(1,d+1):
    s = dd+d
    while s<=h*w:
        acc[s] = calc(s-d,s)+acc[s-d]
        s += d

q = int(input())
for _ in range(q):
    line = input().split(" ")
    l = int(line[0])
    r = int(line[1])

    ret = acc[r] - acc[l]
    print(ret)

Solution (Python):

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for i in range(Q)]
d = [0] * ((H*W)+1)
num_dict = {}
y = 0
for aa in A:
    x = 0
    for a in aa:
        num_dict[a] = [x, y]
        x += 1
    y += 1

for i in range(D+1, H*W+1):
    d[i] = d[i-D] + abs(num_dict[i][0]-num_dict[i-D][0]) + abs(num_dict[i][1]-num_dict[i-D][1])
for l, r in LR:
    print(d[r]-d[l])

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

a = [list(map(int, input().split())) for i in range(h)]

dic = [0] * (h * w)

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

s = [[0] * (h * w // d + 1) for i in range(d)]

for i in range(d):
    for j in range(1, h * w // d + 1):
        b = i + d * (j - 1)
        c = i + d * j

        if c >= len(dic):
            break
        
        y, x = dic[b]
        ny, nx = dic[c]
        s[i][j] = s[i][j - 1] + abs(ny - y) + abs(nx - x)

q = int(input())

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

Solution (Python):
from collections import defaultdict
H, W, D = map(int, input().split())
A = [[] * W for i in range(H)]
dic = {}
for i in range(H):
    a = list(map(int, input().split()))
    A[i] = a
    for j in range(W):
        dic[a[j]] = (i + 1, j + 1)

d = defaultdict(int)
for i in range(D + 1, H * W + 1):
    d[i] = d[i - D] + abs(dic[i][0] - dic[i - D][0]) + abs(dic[i][1] - dic[i - D][1])


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

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

pos=[(0,0) for _ in range(h*w)]

for i in range(h):
    for j,a in enumerate(input().split()):
        pos[int(a)-1]=(i,j)

q=int(input())


distances=[0 for _ in range(h*w)]

for i in range(d,h*w):
    a=h*w-i
    i,j=pos[a-1]
    x,y=pos[a+d-1]
    distances[a-1]=distances[a+d-1]+abs(i-x)+abs(j-y)

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

Solution (Python):
H, W, D = map(int, input().split())
p = {}
for i in range(H):
    for j, value in enumerate(map(int, input().split())):
        p[value] = (i, j)

cost = {}
for i in range(1, W * H + 1):
    cost[i] = cost[i - D] + abs(p[i][0] - p[i - D][0]) + abs(p[i][1] - p[i - D][1]) if i > D else 0

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

Solution (Python):
H, W, D = map(int, input().split())
p = {}
for i in range(H):
    inp = list(map(int, input().split()))
    for j, value in enumerate(inp):
        p[value] = (i, j)

cost = {}
for i in range(1, W * H + 1):
    cost[i] = cost[i - D] + abs(p[i][0] - p[i - D][0]) + abs(p[i][1] - p[i - D][1]) if i > D else 0

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

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

for i in range(H):
	A[i] = list(map(int,input().split()))
rev = [0] * (H * W + 1)
for i in range(H):
	for j in range(W):
		rev[A[i][j]] = i * W + j

cum_sum = [0] * (H * W + 1)
for i in range(1, H * W - D + 1):
	crow = rev[i] // W
	ccol = rev[i] % W
	nrow = rev[i + D] // W
	ncol = rev[i + D] % W
	cum_sum[i + D] = cum_sum[i] + abs(crow - nrow) + abs(ccol - ncol)

Q = int(input())
for i in range(Q):
	L,R = map(int,input().split())
	res = cum_sum[R] - cum_sum[L];
	print(res)

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

pos = {}
for i, row in enumerate(A):
    for j, x in enumerate(row):
        pos[x] = (i, j)

from collections import defaultdict

dt = defaultdict(int)
for x in range(D + 1, H * W + 1):
    y = x - D
    p1 = pos[x]
    p2 = pos[y]
    dt[x] = dt[y] + abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

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

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

a = [list(map(int, input().split())) for i in range(h)]

dic = [0] * (h * w)

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

s = [0] * (h * w)
        
for i in range(d, h * w):
    j = i - d
        
    y, x = dic[j]
    ny, nx = dic[i]
    s[i] = s[i - d] + abs(ny - y) + abs(nx - x)

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=[int(i) for i in input().split()]
a=[]
for i in range(h):
    a.append([int(i) for i in input().split()])
q=int(input())
lr=[]
for i in range(q):
    lr.append([int(i) for i in input().split()])

location_x=[0 for i in range(h*w)]
location_y=[0 for i in range(h*w)]
for i in range(h):
    for j in range(w):
        location_x[a[i][j]-1]=j
        location_y[a[i][j]-1]=i

mpp=[0 for i in range(h*w)]

for i in range(d):
    j=1
    while i+j*d<=h*w-1:
        mpp[ i+j*d]=mpp[ i+j*d-d]+abs(location_x[i+j*d-d]-location_x[i+j*d])+abs(location_y[i+j*d-d]-location_y[i+j*d])
        j+=1

for i in range(q):
    print( mpp[lr[i][1]-1] - mpp[lr[i][0]-1] )

Solution (Python):
H,W,D=map(int,input().split())
d=[[0,0] for i in range(H*W+1)]
d2=[0 for i in range(H*W+1)]
for j in range(H):
  a=[int(x) for x in input().split()]
  for k in range(W):
    d[a[k]]=[j+1,k+1]
for l in range(D+1,H*W+1):
  d2[l]=abs(d[l][0]-d[l-D][0])+abs(d[l][1]-d[l-D][1])
for m in range(D+1,H*W+1):
  d2[m]+=d2[m-D]
Q=int(input())
for i in range(Q):
  a,b=map(int,input().split())
  if a==b:
    print(0)
  else:
    ans=d2[b]-d2[a]
    print(ans)

Solution (Python):
import collections
import itertools
from pprint import pprint as pp

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

Arev = [None] * (H*W+1)
for h in range(H):
  for w in range(W):
    Arev[A[h][w]] = (h,w)

tbl = []
for i in range(D):
  ary = []
  mp = 0
  start = Arev[i+1]
  for x in range(i, H*W, D):
    next_ = Arev[x+1]
    mp += abs(start[0]-next_[0]) + abs(start[1]-next_[1])
    ary.append((x+1,mp))
    start = next_
  tbl.append(ary)


for L,R in LR:
  col1, row = divmod(L, D)
  col2 = R // D
  if row == 0:
    col1 -= 1
    col2 -= 1
  row -= 1
  
  print(tbl[row][col2][1] - tbl[row][col1][1])

Solution (Python):
def mahou(p2, p1):
    return abs(p2[0] - p1[0]) + abs(p2[1] - p1[1])

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

Map = [[0, 0] for i in range(H * W + 1)]
for i in range(len(A)):
    for j in range(len(A[i])):
        Map[A[i][j]] = [i + 1, j + 1]

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

for i in range(D, H * W):
    keiro[i // D][i % D] = mahou(Map[i + 1], Map[i + 1 - D]) + keiro[i // D - 1][i % D]
        
for l, r in LR:
    print(keiro[(r - 1) // D][(r - 1) % D] - keiro[(l - 1) // D][(l - 1) % D])

Solution (Python):
import numpy as np

h, w, d = map(int, input().strip().split(" "))
a = [[int(i) for i in input().strip().split(" ")] for _ in range(h)]
q = int(input().strip())
lr = [input().strip().split(" ") for _ in range(q)]
rs = [None for _ in range(h * w)]
cs = [None for _ in range(h * w)]
for _r, _a in enumerate(a):
    for _c, __a in enumerate(_a):
        rs[__a - 1] = _r
        cs[__a - 1] = _c
rs_d = [rs[i::d] for i in range(d)]
cs_d = [cs[i::d] for i in range(d)]
costs = [
    np.cumsum(
        np.abs(np.array(_rs[1:]) - np.array(_rs[:-1])) +
        np.abs(np.array(_cs[1:]) - np.array(_cs[:-1]))) for _rs, _cs in zip(rs_d, cs_d)
]
for l, r in lr:
    l = int(l) - 1
    r = int(r) - 1
    if l == r:
        print(0)
    elif l < d:
        print(costs[r % d][r // d - 1])
    else:
        print(costs[r % d][r // d - 1] - costs[l % d][l // d - 1])

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

    f(H, W, D, A, Q, LR)


def f(H, W, D, A, Q, LR):
    """
    距離を計算しておく
    """
    pos = [None for _ in range(H * W + 1)]
    for y in range(H):
        for x in range(W):
            a = A[y][x]
            pos[a] = (x, y)

    d = [0 for _ in range(H * W + 1)]
    for i in range(1, D + 1):
        current = i
        dist = 0
        while current + D <= H * W:
            _next = current + D
            i, j = pos[current]
            x, y = pos[_next]

            dist += abs(x - i) + abs(y - j)

            
            d[_next] = dist
            current = _next

    

    for l, r in LR:
        ans = d[r] - d[l]
        print(ans)


if __name__ == '__main__':
    main()

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

poss = [(0, 0)] * (H * W)
for i in range(H):
    for j in range(W):
        poss[As[i][j] - 1] = (i, j)

MPs = [[] for i in range(D)]
for st in range(1, D + 1):
    MPs[st - 1] += [0]
    pi, pj = poss[st - 1]
    for i, j in poss[st - 1 + D::D]:
        MPs[st - 1] += [MPs[st - 1][-1] + abs(i - pi) + abs(j - pj)]
        pi, pj = i, j

for L, R in LRs:
    st = (L - 1) % D + 1
    print(MPs[st - 1][(R - st) // D] - MPs[st - 1][(L - st) // D])

Solution (Python):
H, W, D = map(int, input().split())
 
A = [list(map(int, input().split())) for i in range(H)]
rA = [[0 for j in range(2)] for i in range(H * W + 1)]
S = [0 for i in range(H * W + 1)]
for i in range(H):
	for j in range(W):
		rA[A[i][j]][0] = i
		rA[A[i][j]][1] = j
 
Q = int(input())
for i in range(Q):
	L, R = map(int, input().split())
	ans = 0
	for j in range(H * W) [L::D]:
		if j + D > H * W:
			break
		if S[j]:
			ans += S[j]
			break
		S[j] -= ans
		ans += abs(rA[j + D][1] - rA[j][1]) + abs(rA[j + D][0] - rA[j][0])
	for j in range(H * W)[L::D]:
		if S[j] > 0:
			break
		if j + D > H * W:
			break
		S[j] += ans
	print(S[L] - S[R])

Solution (Python):



H,W,D=[int(i) for i in input().split()]

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

for i in range(H):



    for (j, a) in enumerate(input().split()):

        KAZU[int(a)] = [i,j] 

def cost(x, y):
    return abs(KAZU[x][0] -KAZU[y][0]) + abs(KAZU[x][1] -KAZU[y][1])

COSTMAT=[0]*(H*W+1)
for i in range(H*W+1):
    if i > D:
        COSTMAT[i] = COSTMAT[i-D]+cost(i,i-D)
    else:
        COSTMAT[i] = 0
    
    



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

Solution (Python):
h, w, d = [int(x) for x in input().split()]
a = []
xy = [(0, 0)] * (h * w + 1)
for i in range(h):
  a.append([int(x) for x in input().split()])
  for j in range(w):
    xy[a[i][j]] = (i, j)
q = int(input())
L = []
R = []
for i in range(q):
  l, r = [int(x) for x in input().split()]
  L.append(l)
  R.append(r)

pw = [0] * (h * w + 1)
for i in range(1, d + 1):
  for j in range(d, h * w + 1, d):
    n = i + j
    p = n - d
    if n > h * w:
      break
    pw[n] = pw[p] + abs(xy[n][0] - xy[p][0]) + abs(xy[n][1] - xy[p][1])

for i in range(q):
  print(pw[R[i]] - pw[L[i]])

Solution (Python):
H, W, D = map(int,input().split())
dist = [0]*(H*W+1)
pos = [[0,0] for i in range(H*W+1)]
for i in range(H):
  A = list(map(int,input().split()))
  for j in range(W):
    pos[A[j]] = [i+1, j+1]
    
for i in range(H*W+1-D):
  dist[i] = abs(pos[i][0]-pos[i+D][0])+abs(pos[i][1]-pos[i+D][1])

distances = [[] for i in range(D)]
for i in range(1,H*W+1-D):
  distances[i%D]+=[dist[i]]
distances2 = [[0] for i in range(D)]
for i in range(D):
  for j in range(len(distances[i])):
    distances2[i]+=[distances2[i][-1]+distances[i][j]]

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

Solution (Python):
h,w,d = map(int,input().split())
branch = dict()
for i in range(1,h*w+1):
	branch[i] = []
for i in range(h):
	atemp = list(map(int,input().split()))
	for k in range(w):
		branch[atemp[k]].append(i+1)
		branch[atemp[k]].append(k+1)

q = int(input())
l = []
r = []
for i in range(q):
	ltemp,rtemp = map(int,input().split())
	l.append(ltemp)
	r.append(rtemp)

calc = dict()
for i in range(d):
	calc[i+1] = []
for i in range(1,d+1):
	now = i
	calc[i].append(0)
	k = 0
	while now+d <= h*w:
		calc[i].append(calc[i][k]+abs(branch[now][0]-branch[now+d][0])+abs(branch[now][1]-branch[now+d][1]))
		now = now+d
		k += 1

for i in range(q):
	div = l[i]//d
	if l[i]%d != 0:
		sur = l[i]%d
	else:
		sur = d
	ansdiv = r[i]//d
	if sur == d:
		print(calc[sur][ansdiv-1]-calc[sur][div-1])
	else:
		print(calc[sur][ansdiv]-calc[sur][div])

Solution (Python):

import math
H,W,D = map(int, input().split())



A = [0]*(H*W)
for h in range(H):
    As = list(map(int, input().split()))
    for w in range(W):
        A[As[w]-1] = (h,w)
    
    


Q = int(input())















Ans = [0]*(H*W)
aa = (H*W) // D
bb = (H*W) % D
for dth in range(1,aa+1):
    for d in range(D):
        if dth*D+d >=H*W:
            break
        x,y = A[(dth-1)*D+d]
        x2,y2 = A[dth*D+d]
        ans = abs(x-x2) + abs(y-y2)
        Ans[dth*D+d] = Ans[(dth-1)*D+d] + ans



lrs = []
for q in range(Q):
    L, R = map(int, input().split())
    print(Ans[R-1] - Ans[L-1])

Solution (Python):
H, W, D = map(int,input().split())
dist = [0]*(H*W+1)
pos = [[0,0] for i in range(H*W+1)]
for i in range(H):
  A = list(map(int,input().split()))
  for j in range(W):
    pos[A[j]] = [i+1, j+1]
for i in range(H*W+1-D):
  dist[i] = abs(pos[i][0]-pos[i+D][0])+abs(pos[i][1]-pos[i+D][1])
distances = [[] for i in range(D)]
for i in range(1,H*W+1-D):
  d = dist[i]
  distances[i%D]+=[d]
distances2 = [[0] for i in range(D)]
for i in range(D):
  for j in range(len(distances[i])):
    distances2[i]+=[distances2[i][-1]+distances[i][j]]
Q = int(input())
for i in range(Q):
  L, R = map(int, input().split())
  q = L%D
  l, r = (L-1)//D, (R-1)//D
  print(distances2[q][r]-distances2[q][l])

Solution (Python):
from functools import lru_cache
h, w, d = map(int, input().split())
pos = [[] for j in range(h*w)]
for a in range(h):
    s = list(map(int, input().split()))
    for g in range(w):
        pos[s[g] -1] = [s[g], a+1, g+1]
q = int(input())

def soo(now, start):
    next = now + d
    prevy, prevx = pos[now - 1][1], pos[now - 1][2]
    nexty, nextx = pos[next - 1][1], pos[next - 1][2]
    return ((abs(nexty - prevy) + abs(nextx - prevx)))

def solve(start, end):
    now = 0
    ans = 0
    for i in range(int((end - start) / d)):
        now = start if not now else now + d
        ans += soo(now, start)
    return ans

time = [0 for h in range(h*w)]
for l in range(h*w - d):
    if not time[l + d]:
        time[l+d] = time[l] + (abs(pos[l+d][1] - pos[l][1]) + abs(pos[l+d][2] - pos[l][2]))


@lru_cache(maxsize=None)
def ask(st, en):
    return time[en-1] - time[st-1]


for rr in range(q):
    dd, ff = map(int, input().split())
    print(ask(dd, ff))

Solution (Python):
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[h,w,d]=i2()
a=[]
for i in range(h):
 s=i2()
 for j in range(w):
  a.append([s[j],[i,j]])
q=i1()
lr=[]
for i in range(q):
 lr.append(i2())
 
a=sorted(a)
f=[0 for i in range(h*w)]
for i in range(h*w-d):
  f[i+d]=f[i]+abs(a[i][1][0]-a[i+d][1][0])+abs(a[i][1][1]-a[i+d][1][1])

for i in lr:
 print(f[i[1]-1]-f[i[0]-1])

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

    MAP = {}
    for h in range(H):
        L = list(map(int, input().split()))
        for w in range(W):
            MAP[L[w]] = (h,w)


    A = [0] * (H*W)
    for i in range(D, H*W):
        a, b = MAP[i+1]
        c, d = MAP[i+1-D]
        A[i] = A[i-D] + abs(a-c) + abs(b-d)

    Q = int(input())

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

if __name__ == "__main__":
    solve()

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 = [int(_) for _ in input().split()]
A = [[int(_) for _ in input().split()] for i in range(H)]
Q, = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for i in range(Q)]

"""
H, W, D = 300, 300, 1
Q = 1
A = [[j + i * 300 + 1 for j in range(300)] for i in range(300)]
LR = [[0, 300*300-1], [0, 300*300-1], [0, 300*300-1]]
"""

pos = {}
for i, row in enumerate(A):
    for j, x in enumerate(row):
        pos[x] = (i, j)

dt = [0] * (H * W + 1)
for x in range(1, D + 1):
    r = 0
    while 1:
        dt[x] = r
        y = x + D
        if y > H * W:
            break
        p1 = pos[x]
        p2 = pos[y]
        r += abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
        x = y

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

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

cost = []
for i in range(h) :
    for j in range(w) :
        cost.append([A[i][j], j+1, i+1])

cost.sort(key=lambda c:c[0])


power = [0 for _ in range(h*w)]
for i in range(d) :
    pos = i
    x1 = cost[pos][1]
    y1 = cost[pos][2]
    while pos + d < h*w :
        x2 = cost[pos+d][1]
        y2 = cost[pos+d][2]
        power[pos+d] = power[pos] + abs(x1-x2) + abs(y1-y2)
        pos += d
        x1 = x2
        y1 = y2


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

Solution (Python):
import math

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

coordinate = [[0, 0] for _ in range(H*W+1)]  
for i in range(H):
    A = list(map(int, input().split()))
    for j in range(W):
        coordinate[A[j]] = [i, j]

Q = int(input())
L = []
R = []
for _ in range(Q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)


def dist(coord1, coord2):
    return int(math.fabs(coord1[0] - coord2[0]) + math.fabs(coord1[1] - coord2[1]))


imos = []
imos.append([])
for d in range(1, D+1):
    lst = [0]
    while d + D <= H * W:
        distance = dist(coordinate[d], coordinate[d + D])
        lst.append(distance)
        d += D
    imos.append(lst)

for d in range(1, D+1):
    for i in range(len(imos[d])-1):
        imos[d][i+1] += imos[d][i]

for q in range(Q):
    d = L[q] % D
    if d == 0:
        print(imos[D][int(R[q] / D) - 1] - imos[D][int(L[q] / D) - 1])
    else:
        print(imos[d][int(R[q] / D)] - imos[d][int(L[q] / D)])

Solution (Python):
H, W, D = map(int, input().split())
A = []
C = [0 for _ in range(H * W + 1)]
for h in range(H):
    A.append(list(map(lambda x: int(x) - 1, input().split())))
for i in range(H):
    for j in range(W):
        C[A[i][j]] = (i, j)
h = [0 for _ in range(H * W)]
for i in range(D):
    s = 0
    for j in range(i, H * W, D):
        if j != i:
            n = (C[j][0], C[j][1])
            p = (C[j - D][0], C[j - D][1])
            s += abs(n[0] - p[0]) + abs(n[1] - p[1])
        h[j] = s
Q = int(input())
for _ in range(Q):
    l, r = map(lambda x: int(x) - 1, input().split())
    print(h[r] - h[l])

Solution (Python):
H,W,D = map(int,input().split())
src = [list(map(int,input().split())) for i in range(H)]
Q = int(input())
qs = [tuple(map(int,input().split())) for i in range(Q)]

pos = [[None for i in range(D)] for j in range(H*W//D + 1)]
for y in range(H):
    for x in range(W):
        a = src[y][x]
        b,c = a//D, a%D
        pos[b][c] = (x,y)

cums = [[0] for i in range(D)]
for i in range(D):
    for j in range(H*W//D):
        if pos[j][i] is None or pos[j+1][i] is None:
            cums[i].append(cums[i][-1])
        else:
            x1,y1 = pos[j][i]
            x2,y2 = pos[j+1][i]
            dist = abs(x1-x2) + abs(y1-y2)
            cums[i].append(cums[i][-1] + dist)
            
for l,r in qs:
    d = l%D
    print(cums[d][r//D] - cums[d][l//D])

Solution (Python):
h,w,d = map(int,input().split())
A = [[int(x) for x in input().split()] for x in range(h)]
Q = int(input())
LR = [[int(x) for x in input().split()] for x in range(Q)]
num = [[[0,0] for x in range(h*w//d+1)] for y in range(d)]
for i in range(h):
    for j in range(w):
        n = A[i][j]
        num[n%d][n//d] = [i,j]
numsum = [[0 for x in range(h*w//d+1)] for y in range(d)]

for y in range(d):
    for x in range(1,h*w//d+1):
        a,b = num[y][x-1]
        i,j = num[y][x]
        numsum[y][x] = numsum[y][x-1]+abs(a-i)+abs(b-j)
for l,r in LR:
    print(numsum[r%d][r//d]-numsum[l%d][l//d])

Solution (Python):
h,w,d = map(int,raw_input().split(" "))

mp = {}
now = 0

for a in range(h):
  z = map(int,raw_input().split(" "))
  for zz in z:
    mp[zz] = now
    now += 1

data = [-1] * (h*w + 1)
data2 = [-1] * (h*w + 1)

for a in range(d+1,h*w+1):
  l = mp[a-d]
  r = mp[a]
  x = abs((r/w) - (l/w))
  y = abs((r%w) - (l%w))
  data[a] = x+y
  if a - d <= 0:
    continue
  data2[a] = data2[a-d] + data[a]

q = int(raw_input())

for a in range(q):
  l,r = map(int,raw_input().split(" "))
  print data2[r] - data2[l]

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



n_to_pos = [[0,0]] * (H * W + 1)
for i in range(H):
    for j in range(W):
        n_to_pos[map_[i][j]] = [i,j]

reach_cost = [0] * (H * W + 1)
for i in range(D + 1,H * W + 1):
    reach_cost[i] = reach_cost[i - D] + abs(n_to_pos[i][0] - n_to_pos[i - D][0]) + abs(n_to_pos[i][1] - n_to_pos[i - D][1])

Q = int(input())
for i in range(Q):
    B,E = map(int, input().split())
    print(reach_cost[E]-reach_cost[B])

Solution (Python):
H, W, D = map(int, input().split())
p = {}
for i in range(H):
    inp = list(map(int, input().split()))
    for j, value in enumerate(inp):
        p[value] = (i, j)


cost = {i: 0 for i in range(1, D + 1)}
for i in range(1, D + 1):
    now = i + D
    while now <= H * W:
        cost[now] = cost[now - D] + abs(p[now][0] - p[now - D][0]) + abs(p[now][1] - p[now - D][1])
        now += D



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

Solution (Python):


import itertools


class CumulativeSum(object):
    """Constructs the cumulative sum of the elements in the given sequence.

    :param sequence: The sequence to be processed.
    :type sequence: sequence
    """

    def __init__(self, sequence):
        self.cumulative_sum = [0]
        self.cumulative_sum.extend(itertools.accumulate(sequence))

    def partial_sum(self, first, last):
        """Computes the partial sum of the sequence.

        :param first: The index representing the first element of the
                      subsequence.
        :type first: int
        :param last: The index representing the last element of the
                     subsequence.
        :return: The partial sum.
        """
        return self.cumulative_sum[last + 1] - self.cumulative_sum[first]


def prepare(h, w, d, board):
    val2pos = [None for _ in range(h * w + 1)]
    for r, c in itertools.product(range(h), range(w)):
        val2pos[board[r][c]] = (r, c)
    max_e = h * w // d
    cumsums = []
    for m in range(d):
        max_e = (h * w - m) // d
        costs = []
        for e in range(max_e + 1):
            if e == 0:
                costs.append(0)
            else:
                x0 = (e - 1) * d + m
                if x0 != 0:
                    r0, c0 = val2pos[x0]
                    x1 = e * d + m
                    r1, c1 = val2pos[x1]
                    cost = abs(r1 - r0) + abs(c1 - c0)
                else:
                    cost = 0
                costs.append(cost)
        cumsums.append(CumulativeSum(costs))
    return cumsums


def main():
    h, w, d = (int(x) for x in input().split())
    board = [[int(b) for b in input().split()] for _ in range(h)]
    cumsums = prepare(h, w, d, board)
    q = int(input())
    for _ in range(q):
        l, r = (int(x) for x in input().split())
        dl, ml = divmod(l, d)
        dr, mr = divmod(r, d)
        res = cumsums[ml].partial_sum(dl + 1, dr)
        
        
        print(res)


if __name__ == '__main__':
    main()

Solution (Python):
H, W, D = map(int, input().split())
m = [None] * (H*W+1) 
s = [0] * (H*W+1) 
for y in range(H):
  A = list(map(int, input().split()))
  for x, a in enumerate(A):
    m[a] = (x, y)

for i in range(D+1, H*W+1):
  x, y = m[i]
  px, py = m[i-D]
  s[i] = s[i-D] + abs(x-px) + abs(y-py)

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

Solution (Python):
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
P = [None]*(H*W+1)
for i in range(H):
    for j in range(W):
        P[A[i][j]] = (i, j)
C = [0]*(H*W+1)
for i in range(D+1, H*W+1):
    pi, pj = P[i]; qi, qj = P[i-D]
    C[i] = C[i-D] + abs(pi - qi) + abs(pj - qj)

ans = []
Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    ans.append(C[R] - C[L])
print(*ans, sep='\n')

Solution (Python):
import sys

h, w, d = map(int, input().split())
f = [list(map(int, input().split())) for _ in range(h)]

c_map = [0] * (h * w)
for i in range(h):
    for j in range(w):
        c_map[f[i][j] - 1] = (i, j)

d_map = [0] * (h * w)
for l in range(h * w - d - 1, -1, -1):
    i, j = c_map[l]
    i2, j2 = c_map[l + d]
    d_map[l] = d_map[l + d] + abs(i - i2) + abs(j - j2)

buf = []
q = int(input())
for line in sys.stdin.readlines():
    l, r = map(int, line.split())
    buf.append(d_map[l - 1] - d_map[r - 1])

print('\n'.join(map(str, buf)))

Solution (Python):
import sys

h, w, d = map(int, input().split())
f = [list(map(int, input().split())) for _ in range(h)]

c_map = [0] * (h * w)
for i in range(h):
    for j in range(w):
        c_map[f[i][j] - 1] = (i, j)

d_map = [0] * (h * w)
for l in range(h * w - d - 1, -1, -1):
    i, j = c_map[l]
    i2, j2 = c_map[l + d]
    d_map[l] = d_map[l + d] + abs(i - i2) + abs(j - j2)

buf = []
q = int(input())
for line in sys.stdin.readlines():
    l, r = map(int, line.split())
    buf.append(d_map[l - 1] - d_map[r - 1])

print('\n'.join(map(str, buf)))

Solution (Python):
H,W,D = map(int,raw_input().split())
P = [None]*(H*W+1)
for y in range(H):
  A = map(int,raw_input().split())
  for x in range(W):
    P[A[x]] = (y,x)
B = [0]*(H*W+1)
for i in range(D+1,H*W+1):
  B[i] = B[i-D] + abs(P[i][0]-P[i-D][0])+abs(P[i][1]-P[i-D][1])
Q = input()
ans = 0
for _ in range(Q):
  L,R = map(int,raw_input().split())
  print B[R]-B[L]