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):
H, W, D = map(int, input().split())
A = [0] * H
for i in range(H):
  A[i] = list(map(int, input().split()))
dict = {}
for i in range(H):
  for j in range(W):
    dict[A[i][j]] = [i, j]

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

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

Solution (Python):
import sys
import numpy as np


def main():
    h, w, d = [int(x) for x in input().split()]
    dic = {}
    for i in range(h):
        line = [int(x) for x in input().split()]
        for j, a in enumerate(line):
            dic[a] = (a, i, j)
    magic = [[0] for _ in range(d + 1)]
    for k in range(1, d + 1):
        for m in range(1, h * w):
            if k + (m * d) > h * w:
                break
            magic[k].append(magic[k][m - 1] +
                            abs(dic[k + (m * d)][1] - dic[k + ((m - 1) * d)][1]) +
                            abs(dic[k + (m * d)][2] - dic[k + ((m - 1) * d)][2]))
    q = int(input())
    for _ in range(q):
        l, r = [int(e) for e in input().split()]
        k = d if l % d == 0 else l % d
        print(magic[k][(r - 1) // d] - magic[k][(l - 1) // d])


main()

Solution (Python):
def main():
	H, W, D = map(int,input().split())
	pos = [0]*(H*W)
	for i in range(H):
		A = list(map(int, input().split()))
		for j in range(W):
			pos[A[j]-1] = [i, j]
	Q = int(input())
	lr = [0]*Q
	for i in range(Q):
		lr[i] = list(map(int, input().split()))
	ans = [[0] for _ in range(D)]
	for i in range(H*W-D):
		s_pos = pos[i]
		e_pos = pos[i+D]
		d = abs(s_pos[0]-e_pos[0])+abs(s_pos[1]-e_pos[1])
		ans[i%D].append(ans[i%D][-1]+d)
	for i in range(Q):
		s = lr[i][0]-1
		e = lr[i][1]-1
		print(ans[e%D][e//D]-ans[s%D][s//D])


if __name__ == '__main__':
    main()

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

d = defaultdict(lambda:[])

for i in range(H):
    for j in range(W):
        d[A[i][j]] = [i,j]

cost = defaultdict(lambda:[0])
for r in range(1,D+1):
    for m in range(0,H*W//D):
        if D*(m+1)+r <= H*W:
            cost[r].append(abs(d[D*m+r][0]-d[D*(m+1)+r][0])+abs(d[D*m+r][1]-d[D*(m+1)+r][1]))
for r in range(1,D+1):
    for m in range(len(cost[r])-1):
        cost[r][m+1] += cost[r][m]

Q = int(input())

def magic(L,R):
    r = L%D
    if r == 0:
        r = D
    ml = (L-r)//D
    mr = (R-r)//D
    return cost[r][mr]-cost[r][ml]


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

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

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

ans = [0]*(H*W)
for i in range(D):
    bl = tmp[i][0]
    br = tmp[i][1]
    i += D
    zp = 0
    while i < H*W:
        l = tmp[i][0]
        r = tmp[i][1]
        ans[i] = abs(bl-l)+abs(br-r)+zp
        zp = ans[i]
        bl = l
        br = r
        i += D

jjj = []
for _ in range(Q):
    L,R = [int(i) for i in input().split()]
    jjj.append(ans[R-1]-ans[L-1])

[print(i) for i in jjj]

Solution (Python):
h, w, d = map(int, input().split())
a_array = [[int(x) for x in input().split()] for y in range(h)]
q = int(input())
lr_array = [[int(x) for x in input().split()] for y in range(q)]

whole = []
for i in range(h):
    for j in range(w):
        whole.append([a_array[i][j], i + 1, j + 1])
whole = [[x[1], x[2]] for x in sorted(whole, key=lambda x: x[0])]
diff = [0 for x in range(h * w)]
for i in range(d, h * w):
    if diff[i] != 0:
        continue
    if i == 0:
        continue
    for j in range(i, h * w, d):
        base_x, base_y = whole[j]
        next_x, next_y = whole[j-d]
        diff[j] = diff[j-d]+abs(base_x - next_x) + abs(base_y - next_y)

for l, r in lr_array:
    print(diff[r-1]-diff[l-1])

Solution (Python):
H,W,D = map(int,input().split())
A = {}
for i in range(H):
    l = list(map(int,input().split()))
    for j in range(W):
        A[l[j]] = [i+1,j+1]

Q = int(input())
LR = []
for i in range(Q):
    LR.append(list(map(int,input().split())))


ru = {}
for i in range(1,D+1):
    ru[i] = [0]

for i in range(1,D+1):
    c = 1
    while i + D*c <= H*W:
        now = A[i+D*(c-1)]
        will = A[i+D*c]
        mp = abs(will[0] - now[0]) + abs(will[1] - now[1])
        ru[i].append(mp + ru[i][c-1])
        c += 1

for i in range(Q):
    t = LR[i][0] % D
    if t == 0:
        t = D
        print(ru[t][LR[i][1]//D-1] - ru[t][LR[i][0]//D-1])
    else:
        print(ru[t][LR[i][1]//D] - ru[t][LR[i][0]//D])

Solution (Python):
h, w, d = map(int, input().split())
d_x = [-1] * (h*w + 1)
d_y = [-1] * (h*w + 1)
for i in range(h):
    tmp = list(map(int, input().split()))
    for j in range(len(tmp)):
        d_x[tmp[j]] = i
        d_y[tmp[j]] = j

dist = [-1] * (h*w + 1) 
for i in range(h*w):
    j = h*w - i
    if h*w - j < d:
        dist[j] = 0
    else:
        dist[j] = dist[j+d] + abs(d_x[j+d] - d_x[j]) + abs(d_y[j+d] - d_y[j])
    
q =  int(input())
for _ in range(q):
    start, end = map(int, input().split())
    print(dist[start]- dist[end])

Solution (Python):
from functools import partial
from itertools import islice


def take(n, iterable):
    return list(islice(iterable, n))


def chunked(iterable, n):
    return iter(partial(take, n, iter(iterable)), [])


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


def solve(s):
    h, w, d, *aqlr = map(int, s.split())
    a, q, lr = aqlr[:h * w], aqlr[h * w], aqlr[h * w + 1:]
    n = h * w
    pos = [0] * (n + 1)
    for i, _a in enumerate(a):
        pos[_a] = (i // w, i % w)
    cost = [0] * (n + 1)
    for i in range(d + 1, n + 1):
        cost[i] = cost[i - d] + distance(pos[i - d], pos[i])
    return "\n".join(["%d" % (cost[r] - cost[l]) for l, r in chunked(lr, 2)])


n, m, d = map(int, input().split())
l = '{} {} {}\n'.format(n, m, d) + '\n'.join([input() for _ in range(n)])
q, = map(int, input().split())
l += '\n{}\n'.format(q) + '\n'.join([input() for _ in range(q)])
print(solve(l))

Solution (Python):
from functools import partial
from itertools import islice


def take(n, iterable):
    return list(islice(iterable, n))


def chunked(iterable, n):
    return iter(partial(take, n, iter(iterable)), [])


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


def solve(s):
    h, w, d, *aqlr = map(int, s.split())
    a, q, lr = aqlr[:h * w], aqlr[h * w], aqlr[h * w + 1:]
    n = h * w
    pos = [0] * (n + 1)
    for i, _a in enumerate(a):
        pos[_a] = (i // w, i % w)
    cost = [0] * (n + 1)
    for i in range(d + 1, n + 1):
        cost[i] = cost[i-d]+distance(pos[i - d], pos[i])
    ans = []
    for l, r in chunked(lr, 2):
        ans.append("%d" % (cost[r] - cost[l]))
    return "\n".join(ans)


n, m, d = map(int, input().split())
l = '{} {} {}\n'.format(n, m, d) + '\n'.join([input() for _ in range(n)])
q, = map(int, input().split())
l += '\n{}\n'.format(q) + '\n'.join([input() for _ in range(q)])
print(solve(l))

Solution (Python):
import sys
fastinput = sys.stdin.readline
H,W,D = [int(_) for _ in input().split()]
row=((H*W)//D+1)
modD = [[(0,0)]*row for i in range(D)] 
for h in range(H):
    A=[int(__) for __ in fastinput().split()]
    for w,a in enumerate(A):
        y,x = (a-1)//D,(a-1)%D
        modD[x][y]=(h,w)
costs=[[0]*row for i in range(D)]
for d in range(D):
    pre=(0,0)
    curcos=0
    for k in range(row):
        now=modD[d][k]
        curcos += abs(now[0]-pre[0]) + abs(now[1]-pre[1])
        costs[d][k]=curcos
        pre=now
Q=int(input())
for _ in range(Q):
    s,g=[int(i)-1 for i in fastinput().split()]
    amari=s%D
    sRow,gRow=s//D,g//D
    print(costs[amari][gRow]-costs[amari][sRow])

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

Solution (Python):
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations
from bisect import bisect_left, bisect_right


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W
 

dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")



H, W, D = l_inpl()
A = {}

for hi in range(H):
    l = l_inpl()
    for wi in range(W):
        A[l[wi]] = [wi, hi]

Q = i_inpl()
LR = []
for _ in range(Q):
    LRi = l_inpl()
    LR.append(LRi)

power = []
for i in range(1, H*W-D+1):
    power.append(abs(A[i+D][0] - A[i][0]) + abs(A[i+D][1] - A[i][1]))
    
r_cumsum = [0] * D
for i in range(len(power)):
    r_cumsum.append(r_cumsum[i] + power[len(power)-i-1])

cumsum = r_cumsum[::-1]

for l, r in LR:
    print(cumsum[l-1] - cumsum[r-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)]

number_dict = {}
for h in range(H):
    for w in range(W):
        number_dict[A[h][w]] = (w+1, h+1)
        
        
number = [0 for _ in range(H*W+1)]
for i in range(H*W):
    now = H * W - i
    
    if now + D > H * W:
        pass
    
    else:
        number[now] = number[now + D] + abs(number_dict[now+D][0] - number_dict[now][0]) + abs(number_dict[now+D][1] - number_dict[now][1])
       

for i in range(Q):
    res = number[LR[i][0]] - number[LR[i][1]]
            
    print(res)

Solution (Python):



def main():
    h, w, d = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    pieces = [0] * (h * w + 1)
    cost = [0 for _ in range(h * w + 1)]

    for hi in range(h):
        for wi in range(w):
            number = a[hi][wi]
            pieces[number] = (hi, wi)

    
    
    
    for i in range(d + 1, h * w + 1):
        prev_piece = pieces[i - d]
        next_piece = pieces[i]

        cost[i] = cost[i - d] + \
            abs(next_piece[1] - prev_piece[1]) + \
            abs(next_piece[0] - prev_piece[0])

    q = int(input())
    ans = [0 for _ in range(q)]

    for j in range(q):
        lj, rj = map(int, input().split())
        ans[j] = cost[rj] - cost[lj]

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


if __name__ == '__main__':
    main()

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

h, w, d = [ int(v) for v in input().split() ]
def manhattan(intuple1,intuple2):
	return abs(intuple1[2]-intuple2[2]) + abs(intuple1[1]-intuple2[1])

grid_list = [ None for i in range(w*h) ]
for i in range(h):
	num_list = [ int(v) for v in input().split() ]
	for j in range(w):
		grid_list[i*w+j] = (num_list[j],i,j)
grid_list = sorted(grid_list)

sum_list = []

for i in range(1,d+1):
	temp_list = []
	left = i
	s = 0
	for j in range(i,w*h+1,d):
		s +=  manhattan(grid_list[left-1],grid_list[j-1])
		temp_list.append(s)

		left = j
	sum_list.append(temp_list)

m = int(input())
for i in range(m):
	l, r = [ int(v) for v in input().split() ]
	print(sum_list[r%d-1][(r-1)//d]-sum_list[l%d-1][(l-1)//d])

Solution (Python):
from operator import itemgetter

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

for i in range(H):
    x = [int(x) for x in input().split()]
    for ind,j in enumerate(x):
        a.append([j,i,ind])
a.sort(key=itemgetter(0))
Q = int(input())
LR = [[int(x) for x in input().split()]for _ in range(Q)]

stims = [[[0,0,0]]for _ in range(D)]
dinds = [{}for _ in range(D)]
for i in a:
    d = i[0]%D
    stims[d].append([stims[d][-1][0]+abs(i[1]-stims[d][-1][1])+abs(i[2]-stims[d][-1][2]),i[1],i[2]])
    dinds[d][i[0]]=len(stims[d])-1

for i in LR:
    dnum = i[0]%D
    l = dinds[dnum][i[0]]
    r = dinds[dnum][i[1]]
    print(stims[dnum][r][0]-stims[dnum][l][0])

Solution (Python):
from operator import itemgetter

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

for i in range(H):
    x = [int(x) for x in input().split()]
    for ind,j in enumerate(x):
        a.append([j,i,ind])
a.sort(key=itemgetter(0))
Q = int(input())
LR = [[int(x) for x in input().split()]for _ in range(Q)]

stims = [[[0,0,0]]for _ in range(D)]
dinds = [{}for _ in range(D)]
for i in a:
    d = i[0]%D
    stims[d].append([stims[d][-1][0]+abs(i[1]-stims[d][-1][1])+abs(i[2]-stims[d][-1][2]),i[1],i[2]])
    dinds[d][i[0]]=len(stims[d])-1

for i in LR:
    dnum = i[0]%D
    l = dinds[dnum][i[0]]
    r = dinds[dnum][i[1]]
    print(stims[dnum][r][0]-stims[dnum][l][0])

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

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

B = [0 for i in range(H*W)]

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

Q = int(input())

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

DS = [[0] for i in range(D)]
for i in range(D):
    ds = 0
    j=1
    while j*D + i <H*W:
        ds+=abs(B[j*D + i][0]-B[(j-1)*D + i][0])+abs(B[j*D + i][1]-B[(j-1)*D + i][1])
        DS[i].append(ds)
        j+=1

for i in range(Q):
    l,r=C[i]
    l=l-1
    r=r-1
    q=l%D
    print(DS[q][r//D]-DS[q][l//D])

Solution (Python):
h,w,d=map(int,input().split())
l=[list(map(int,input().split())) for i in range(h)]
L=[0 for i in range(h*w)]
for i in range(h):
  for j in range(w):
    L[l[i][j]-1]=[i,j]

sumL=[0 for i in range(h*w+1)]
for i in range(h*w):
  if i>=d:
    sumL[i+1]=sumL[i+1-d]+abs(L[i][0]-L[i-d][0])+abs(L[i][1]-L[i-d][1])

q=int(input())
QL=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  print(sumL[QL[i][1]]-sumL[QL[i][0]])

Solution (Python):
H,W,D=map(int,input().split())
MAP=[list(map(int,input().split())) for i in range(H)]
Q=int(input())
data=dict()
from collections import defaultdict
cost=defaultdict(int)
for i in range(H):
    for j in range(W):
        data[MAP[i][j]]=(i,j)
for i in range(1,D+1):
    bef=i
    now=i
    c=0
    cost[i]=0
    while now+D<=H*W:
        bef,now=now,now+D
        c+=abs(data[now][0]-data[bef][0])+abs(data[now][1]-data[bef][1])
        cost[now]=c
def solve():
    L,R=map(int,input().split())
    return cost[R]-cost[L]
for q in range(Q):
    print(solve())

Solution (Python):
H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for i in range(H)]
d = [[0,0,0] for _ in range(H*W+2)]
for h in range(H):
    for w in range(W):
        d[A[h][w]+1] = [h+1,w+1,0]
d = d[2:]
for i in range(H*W):
    if i < D:
        continue
    d[i][2] = d[i-D][2]+abs(d[i][0]-d[i-D][0])+abs(d[i][1]-d[i-D][1])
q = int(input())
for i in range(q):
    l,r = map(int,input().split())
    print(d[r-1][2]-d[l-1][2])

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)]


coord = {}
for i in range(h):
    for j in range(w):
        a_ij = a[i][j] - 1
        coord[a_ij] = (i, j)

import math
cost = [[0 for i in range(int(math.ceil(h * w / d)))] for i in range(d)]
for i in range(h * w - d):
    i0 = int(i / d)
    i1 = int(i % d)
    cost[i1][i0] = abs(coord[i + d][0] - coord[i][0]) + abs(coord[i + d][1] - coord[i][1])

cost_sum = [[0 for i in range(int(math.ceil(h * w / d)))] for i in range(d)]
for i in range(d):
    for j in range(int(math.ceil(h * w / d))):
        if j != 0:
            cost_sum[i][j] = cost_sum[i][j-1] + cost[i][j-1]
        else:
            cost_sum[i][j] = 0

for i in range(q):
    l = lr[i][0] - 1
    r = lr[i][1] - 1

    _cost_sum = cost_sum[int(l % d)]
    print(_cost_sum[int(r / d)] - _cost_sum[int(l / d)])

Solution (Python):

from collections import defaultdict


def main():
    high, width, d = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(high)]

    land_dic = defaultdict(tuple)
    for i in range(high):
        for j in range(width):
            num = data[i][j]
            land_dic[num] = (i, j)

    dp = [0 for i in range(high * width + 1)]
    for i in range(d + 1, high * width + 1):
        now_num = i
        pre_num = i - d
        now_place = land_dic[now_num]
        pre_place = land_dic[pre_num]
        dist = abs(now_place[0] - pre_place[0]) + abs(now_place[1] - pre_place[1])
        dp[i] = dp[i - d] + dist

    q_num = int(input())
    for i in range(q_num):
        start, goal = map(int, input().split())
        print(dp[goal] - dp[start])





if __name__ == '__main__':
    main()

Solution (Python):
H, W, D = [int(i) for i in input().split()]
B = [(-1, -1) for _ in range(H * W)]
for h in range(H):
    A = [int(i) - 1 for i in input().split()]
    for w in range(W):
        B[A[w]] = (h, w)

C = [0] * (H * W)
for i in range(D, H * W):
    h, w = B[i - D]
    nh, nw = B[i]
    C[i] = C[i - D] + abs(nh - h) + abs(nw - w)

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

Solution (Python):
def sol():
    h,w,d=map(int,input().split())
    a=[[int(i) for i in input().split()] for i in range(h)]
    t={}
    for i in range(h):
        for j in range(w):
            t[a[i][j]]=(i,j)
    ans=[0]*(h*w+1)
    for i in range(h*w,d,-1):
        o,p=t[i]
        ans[i-d]=ans[i]+abs(o-t[i-d][0])+abs(p-t[i-d][1])
    q=int(input())
    for i in range(q):
        l,r=map(int,input().split())
        print(ans[l]-ans[r])

if __name__=="__main__":
    sol()

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

for y in range(H):
    position = list(map(int, input().split()))
    for x in range(W):
        positions[position[x]-1] = [x, y]

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

answers = [[] for _ in range(D)]
d_length = (H * W) // D + 1
for d in range(D):
    current = d
    d_answers = [0 for _ in range(d_length)]
    idx = 1
    while current + D < H * W:
        d_answers[idx] = get_distance(current, current+D) + d_answers[idx-1]
        current += D
        idx += 1
    answers[d] = d_answers

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

Solution (Python):
h, w, d = map(int,input().split())
a = [list(map(int,input().split()))for _ in range(h)]
pos = dict()
for i in range(h):
  for j in range(w):
    pos[a[i][j] - 1] = (i, j)
dis = [[0] for _ in range(d)]
for i in range(d):
  num = i
  while num < h * w - d:
    p = pos[num]
    nextp = pos[num + d]
    dis[i - 1].append(abs(nextp[0] - p[0]) + abs(nextp[1] - p[1]))
    num += d
for i in range(d):
  for j in range(len(dis[i])-1):
    dis[i][j + 1] += dis[i][j]
q = int(input())
for i in range(q):
  l, r = map(lambda x:int(x)-1, input().split())
  print(dis[l % d - 1][r // d] - dis[l % d - 1][l // d])

Solution (Python):
h, w, d = map(int,input().split())
a = [list(map(int,input().split()))for _ in range(h)]
pos = dict()
for i in range(h):
  for j in range(w):
    pos[a[i][j] - 1] = (i, j)
dis = [[0] for _ in range(d)]
for i in range(d):
  num = i
  while num < h * w - d:
    p = pos[num]
    nextp = pos[num + d]
    dis[i - 1].append(abs(nextp[0] - p[0]) + abs(nextp[1] - p[1]))
    num += d
for i in range(d):
  for j in range(len(dis[i])-1):
    dis[i][j + 1] += dis[i][j]
q = int(input())
for i in range(q):
  l, r = map(lambda x:int(x)-1, input().split())
  print(dis[l % d - 1][r // d] - dis[l % d - 1][l // d])

Solution (Python):
h,w,k=map(int,input().split())
pos=[0]*(h*w+1)
for i in range(h):
  tmp=list(map(int,input().split()))
  for j in range(w):
    pos[tmp[j]]=[i+1,j+1]
cs=[[0] for _ in range(k+1)]
for i in range(1,k+1):
  for j in range(1,(h*w-i)//k+1):
    x1,y1=pos[i+k*(j-1)][1],pos[i+k*(j-1)][0]
    x2,y2=pos[i+k*j][1],pos[i+k*j][0]
    cs[i].append(abs(y2-y1)+abs(x2-x1)+cs[i][j-1])
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  tmp=l%k
  if tmp==0:
    tmp=k
  l,r=(l-tmp)//k,(r-tmp)//k
  print(cs[tmp][r]-cs[tmp][l])

Solution (Python):


from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)





def main():
    h, w, d = intin()
    alistlist = []
    for i in range(h):
        alistlist.append(intina())
    q = intin()
    lrlist = intinl(q)

    blist = {0: (0, 0)}
    for i, alist in enumerate(alistlist):
        for j, a in enumerate(alist):
            blist[a] = (i, j)

    slistlist = []
    hwmax = h * w

    for i in range(d):
        slist = [0]
        a = i
        magicsum = 0
        while True:
            anext = a + d
            if anext > hwmax:
                break
            magicsum += abs(blist[a][0] - blist[anext][0]) + \
                        abs(blist[a][1] - blist[anext][1])
            slist.append(magicsum)
            a = anext
        slistlist.append(slist)

    for l, r in lrlist:
        slist = slistlist[l % d]
        print(slist[r // d] - slist[l // d])


if __name__ == '__main__':
    main()

Solution (Python):

def main():
    buf = input()
    buflist = buf.split()
    H = int(buflist[0])
    W = int(buflist[1])
    D = int(buflist[2])
    board = []
    for i in range(H):
        buf = input()
        buflist = buf.split()
        board.append(list(map(int, buflist)))
    buf = input()
    Q = int(buf)
    query = []
    for i in range(Q):
        buf = input()
        buflist = buf.split()
        L = int(buflist[0])
        R = int(buflist[1])
        query.append((L, R))
    moddivxy = []
    for i in range(H):
        for j in range(W):
            moddivxy.append((board[i][j] % D, board[i][j] // D, i, j))
    moddivxy = list(sorted(moddivxy))
    mp_table = [[0]]
    mod = 0
    last_xy = (-1, -1)
    for x in moddivxy:
        if x[0] == 0 and x[1] == 1: 
            mp_table[mod].append(0)
        elif x[0] > mod:
            mod = x[0]
            mp_table.append([0])
        else:
            mp_table[mod].append(mp_table[mod][-1] + abs(last_xy[0] - x[2]) + abs(last_xy[1] - x[3]))
        last_xy = (x[2], x[3])
    for q in query:
        m = q[0] % D
        d_start = q[0] // D
        d_end = q[1] // D
        print(mp_table[m][d_end] - mp_table[m][d_start])


if __name__ == '__main__':
    main()

Solution (Python):
H,W,D = list(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 = [None]*(H*W+1) 
for h, row in enumerate(A):
  for w, a in enumerate(row):
    
    X[a] = (h+1,w+1)

Y = [0]*(H*W+1) 
for d in range(1,D+1):
  x = d
  while x+D <= H*W:
    Y[x+D] = Y[x] + abs(X[x+D][0]-X[x][0]) + abs(X[x+D][1]-X[x][1])
    x+=D

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

Solution (Python):

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

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

for i in range(H):
    a=list(map(int,input().split()))
    for j in range(W):
        mp[a[j]]=[i,j]
S = []
for i in range(1,D+1):
    s1 = [0]
    s2 = 0
    j=1
    while j*D+i<=H*W:
        s2+=abs(mp[j*D+i][0]-mp[(j-1)*D+i][0])+abs(mp[j*D+i][1]-mp[(j-1)*D+i][1])
        s1.append(s2)
        j+=1
    S.append(s1)
ans=[]
Q=int(input())
for i in range(Q):
    L,R=list(map(int,input().split()))
    d=(L-1)%D
    e=(R-1)//D
    f=(L-1)//D
    ans.append(S[d][e]-S[d][f])
    
for a in ans:
    print(a)

Solution (Python):
n=0
h,w,d=map(int,input().split())
x=[0]*(h*w)
y=[0]*(h*w)
for i in range(h):
    for a in input().split():
        A=int(a)-1
        x[A]=n%w
        y[A]=n//w
        n+=1
        
c=[0]*(h*w)
for i in range(h*w):
    if i>=d:
        c[i]=c[i-d]+abs(x[i]-x[i-d])+abs(y[i]-y[i-d])
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(c[r-1]-c[l-1])

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

H,W,D = map(int,input().split())
N = H*W
ND = N//D


X = np.zeros((D,ND+1),dtype=np.int64)
Y = np.zeros((D,ND+1),dtype=np.int64)

for x in range(H):
  row = input()
  for y,n in enumerate(row.split()):
    n = int(n)
    q,r = n//D,n%D
    X[r,q] = x
    Y[r,q] = y


MAGIC = np.zeros_like(X)
MAGIC[:,1:] = (np.abs(np.diff(X,axis = 1)) + np.abs(np.diff(Y,axis = 1))).cumsum(axis = 1)

Q = int(input())
for _ in range(Q):
  l,r = map(int,input().split())
  d = l%D
  print(MAGIC[d,r//D] - MAGIC[d,l//D])

Solution (Python):
from itertools import*
from collections import*
h,w,d=map(int,input().split())
g=defaultdict(tuple)
f=defaultdict(int)
for i in range(h):
    for j,v in enumerate(map(int,input().split())):
        g[v]=(i,j)
        
q=int(input())

for i in range(1,d+1):
    for k,v in enumerate(accumulate([0]+[sum(abs(s-t)for s,t in zip(g[j+d],g[j]))for j in range(i,h*w+1-d,d)])):
        f[i+k*d]=v
        
for i in range(q):
    l,r=map(int,input().split())
    print(f[r]-f[l])

Solution (Python):

H,W,D=map(int,raw_input().split())
A=[None]
for i in range(H):
    b=map(int,raw_input().split())
    A.append([None]+b)
Q=int(raw_input())
L=[];R=[]
for i in range(Q):
    l,r=map(int,raw_input().split())
    L.append(l);R.append(r)

P={}
for i in range(1,H+1):
    for j in range(1,W+1):
        P[A[i][j]]=(i,j)
C={}
for d in range(1,D+1):
    x=d
    cost=0
    C[d]=0
    while x+D<=H*W:
        n=x+D
        np=P[n];pp=P[x]
        distance=abs(np[0]-pp[0])+abs(np[1]-pp[1])
        cost+=distance
        C[n]=cost
        x=n
for l,r in zip(L,R):
    print(C[r]-C[l])

Solution (Python):
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
As = [(0, 0, 0)]
for i in range(H):
    for j in range(W):
        As.append((A[i][j], i+1, j+1))
Q = int(input())
Qs = [list(map(int, input().split())) for _ in range(Q)]
As.sort()
dp = [0] * (H*W+1)
for i in range(1, H*W+1- D):
    a1, j, k = As[i]
    a2, x, y = As[i+D]
    dp[i+D] = dp[i] + abs(x-j) + abs(y-k)
    
for l, r in Qs:
    print(dp[r] -dp[l])

Solution (Python):
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
As = [(0, 0, 0)]
for i in range(H):
    for j in range(W):
        As.append((A[i][j], i+1, j+1))
Q = int(input())
Qs = [list(map(int, input().split())) for _ in range(Q)]
As.sort()
dp = [0] * (H*W+1)
for i in range(1, H*W+1- D):
    a1, j, k = As[i]
    a2, x, y = As[i+D]
    dp[i+D] = dp[i] + abs(x-j) + abs(y-k)
    
for l, r in Qs:
    print(dp[r] -dp[l])