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):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
INF = float("inf")
import sys
sys.setrecursionlimit(10000)

def manhattan(y1, x1, y2, x2): return abs(y1 - y2) + abs(x1 - x2)


def solve(H, W, D, A, query):
    num_pos = dict()
    for y in range(H):
        for x in range(W):
            num_pos[A[y][x]] = (y, x)

    dp = [None] * (H * W + 1)
    for i in range(1, D + 1):
        dp[i] = 0
        for j in range(i + D, len(dp), D):
            y1, x1 = num_pos[j - D]
            y2, x2 = num_pos[j]
            dp[j] = dp[j - D] + manhattan(y1, x1, y2, x2)

    for q in query:
        L, R = q
        print(dp[R] - dp[L])


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

    solve(H, W, D, A, query)


if __name__ == "__main__":
    main()

Solution (Python):


import numpy as np

def diff(pos1, pos2):
    return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])

H, W, D = map(int, input().split())
pos = dict()
for i in range(H):
    buf = list(map(int, input().split()))
    for j in range(W):
        pos[buf[j]] = (i, j)
        
Q = int(input())
query = []
for _ in range(Q):
    l, r = map(int, input().split())
    query.append((l, r))
        
cost = np.zeros(H * W + 1).astype(int)
for i in range(1, D + 1):
    cost[i] = 0
    x = i + D
    while x <= H * W:
        cost[x] = cost[x - D] + diff(pos[x - D], pos[x])
        x += D
        
for l, r in query:
    print(cost[r] - cost[l])

Solution (Python):
H,W,D = list(map(int, input().split()))
X = [[0,0] for i in range(H*W+1)]

for i in range(1, H+1):
	A = list(map(int, input().split()))
	for idx, a in enumerate(A):
		X[a] = [i, idx+1]

Q = int(input())
L = []
R = []
S = [0]*(H*W+1)

for i in range(Q):
	l,r = list(map(int, input().split()))
	L.append(l)
	R.append(r)

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

for i in range(Q):
	print(S[R[i]] - S[L[i]])

Solution (Python):
h,w,d = [int (i) for i in input().split()]
index = [[0,0] for i in range(h*w)]
sum = 0
for i in range(h):
    temp = [int(i) for i in input().split()]
    for j in range(w):
        index[temp[j]-1][0] = i
        index[temp[j]-1][1] = j
q = int(input())
dick = [0 for i in range (h*w)]
for i in range (d,h*w):
    dick[i] = dick[i-d] + abs(index[i][0]-index[i-d][0])+abs(index[i][1]-index[i-d][1])
for i in range(q):
    a,b = [int(i) for i in input().split()]
    print(dick[b-1] - dick[a-1])

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

I = [0] * (w * h + 1)
for i in range(h):
    for j in range(w):
        I[A[i][j]] = (i, j)
D = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
    D[i] = D[i - d] + abs(I[i][0] - I[i - d][0]) + abs(I[i][1] - I[i - d][1])
s = []
g = []
for i in range(q):
    s, g = map(int, input().split())
    print(D[g] - D[s])

Solution (Python):
H,W,D=list(map(int,input().split()))
X=[(0,0) for i in range(H*W+1)]

for i in range(1,H+1):
	A=list(map(int,input().split()))
	for idx,a in enumerate(A):
		X[a]=(i,idx+1)

Q=int(input())
L=[]
R=[]
S=[0]*(H*W+1)

for i in range(Q):
	l,r=list(map(int,input().split()))
	L.append(l)
	R.append(r)

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

for i in range(Q):
	print(S[R[i]]-S[L[i]])

Solution (Python):

import math

if __name__ == "__main__":
	H, W, D = list(map(int, input().split()))
	masu = {}
	for i in range(H):
		inputs = list(map(int, input().split()))
		for j in range(W):
			masu[inputs[j]] = [i, j]

	Q = int(input())
	L = []
	R = []
	for i in range(Q):
		l, r = list(map(int, input().split()))
		L.append(l)
		R.append(r)
	
	S = [0] * (H*W+1)
	for i in range(D+1, H*W+1):
		S[i] = S[i-D] + abs(masu[i][0]-masu[i-D][0]) + abs(masu[i][1]-masu[i-D][1])
	
	for i in range(Q):
		print(S[R[i]] - S[L[i]])

Solution (Python):
tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dictx ={}
dicty ={}
for i in range(H):
    tmp = input().split()
    for d in range(W):
        dictx[tmp[d]] = i
        dicty[tmp[d]] = d
cost ={}
def calcost(R):
    if int(R)<=D:
        cost[R] = 0
        return 0
    else:
        costs = abs(dictx[R]-dictx[str(int(R)-D)]) + abs(dicty[R]-dicty[str(int(R)-D)])
        cost[R] = costs + cost[str(int(R)-D)]
        return cost[R]

for n in range(1,H*W+1):
    calcost(str(n))
Q = int(input())
for j in range(Q):
    tmp = input().split()
    print(str(cost[tmp[1]]-cost[tmp[0]]))

Solution (Python):
H,W,D = [int(n) for n in raw_input().split(" ")]
Location = {}
for h in range(1,H + 1):
	A = [int(n) for n in raw_input().split(" ")]
	for w, a in enumerate(A):
		Location[a] = (h, w+1)
Q = int(raw_input())
L = [None] * (Q+1)
R = [None] * (Q+1)
for q in range(1,Q+1):
	L[q], R[q] = [int(n) for n in raw_input().split(" ")]



C = {}
for d in range(1,D+1):
	C[d,d] = 0
	cur_dist = 0
	for x1 in range(d, H * W + 1, D):
		x2 = x1 + D
		if x2 > H * W: 
			break
		h1, w1 = Location[x1]
		h2, w2 = Location[x2]
		
		cur_dist = cur_dist + abs(h1 - h2) + abs(w1 - w2)
		C[(d,x2)] = cur_dist
	
for q in range(1,Q+1):
	l, r = L[q], R[q]
	d = l % D
	if d == 0: 
		d = D
	print (C[(d,r)] - C[(d,l)])

Solution (Python):
H, W, D = [int(x) for x in input().split()]
size = H*W+1
c = [(-1, -1)] * size
p = [0] * size

for y in range(H):
    for x, a in enumerate([int(s) for s in input().split()]):
        c[a] = (x, y)

for a in range(D+1, size):
    p[a] = p[a-D] + abs(c[a][0] - c[a-D][0]) + abs(c[a][1] - c[a-D][1])

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

Solution (Python):
def dist(p,q):
    return abs(p[0]-q[0]) + abs(p[1]-q[1])

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

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

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


    pre = [[0 for j in range((2*H*W)//D)  ] for i in range(D)]
    for i in range(D,H*W):
        pre[i%D][i//D] = pre[i%D][i//D - 1] + dist(pos[i], pos[i-D])

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

        v = pre[L%D]
        print(v[R//D] - v[L//D])

if __name__ == '__main__':
    main()

Solution (Python):
h, w, d = map(int, raw_input().split())
a = [map(int, raw_input().split()) for _ in xrange(h)]
r = {a[x][y]: (x, y) for x in xrange(h) for y in xrange(w)}
b = [0] * (h * w + 1)
for _ in xrange(d + 1, h * w + 1):
    b[_] = b[_ - d] + sum([abs(r[_ - d][i] - r[_][i]) for i in [0, 1]])
for _ in xrange(input()):
    l, r = map(int, raw_input().split())
    print b[r] - b[l]

Solution (Python):
def telepo_test(start, goal, delta, board):
    route = [start + delta * i for i in range(abs(goal - start) // abs(delta) + 1)]
    route = [board[r] for r in route]

    mp = 0
    for s, t in zip(route[:-1], route[1:]):
        print(s,t)
        mp += abs(t[0] - s[0]) + abs(t[1] - s[1])
    return mp


H, W, D = tuple(map(int, input().split()))
board = dict()
for h in range(H):
    row = tuple(map(int, input().split()))
    for w in range(W):
        board[row[w]] = (h, w)
delta = dict([(i, 0) for i in range(1, D+1)])
for d in range(D+1, H*W+1):
    delta[d] = delta[d-D] + abs(board[d][0] - board[d-D][0]) + abs(board[d][1] - board[d-D][1])

Q = int(input())

LRs = [tuple(map(int, input().split())) for _ in range(Q)]
result = [delta[LR[1]] - delta[LR[0]] for LR in LRs]

for r in result:
    print(r)

Solution (Python):
def get_next_int():
    return int(float(input()))
def get_next_ints(delim=" "):
    return tuple([int(float(x)) for x in input().split(delim)])

def main():
    h, w, d = get_next_ints()
    values = {}
    for i in range(h):
        line_data = get_next_ints()
        for j, a in enumerate(line_data):
            values[a] = (i, j)
    from collections import defaultdict
    distances = defaultdict(int)
    
    for a in range(1,h * w + 1):
        i, j = values[a]
        prev = a - d
        if prev in values:
            prev_i, prev_j = values[prev]
            distances[a] = abs(prev_i - i) + abs(prev_j - j) + distances[prev]
        else:
            distances[a] = 0
    q = get_next_int()
    for k in range(q):
        r, l = get_next_ints()
        print(distances[l] - distances[r] )
        
if __name__ == '__main__':
    main()

Solution (Python):
from itertools import chain

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

x_a = [0] * (H*W)
y_a = [0] * (H*W)

for i, ax in enumerate(A):
    for j, ay in enumerate(ax):
        x_a[ay-1] = i
        y_a[ay-1] = j

S = [0] * (H*W)
for i in reversed(range(H*W-D)):
    S[i] = abs(x_a[i] - x_a[i+D]) + abs(y_a[i] - y_a[i+D]) + S[i + D]

for L, R in exam:
    print(S[L-1] - S[R-1])

Solution (Python):
def main():
    H, W, D = map(int, input().split())
    A = tuple(tuple(map(int, input().split())) for _ in [0] * H)
    Q = int(input())
    LR = tuple(tuple(map(int, input().split())) for _ in [0] * Q)

    grid = dict()
    for i, a in enumerate(A):
        for j, b in enumerate(a):
            grid[b] = (i + 1, j + 1)

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

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

main()

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

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

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

Q=input()
for i in range(Q):
	L,R=map(int,raw_input().split())
	print dist[R]-dist[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 + (i < h * w % d)) for i in range(d)]

for i in range(d):
    for j in range(1, len(s[i])):
        b = i + d * (j - 1)
        c = i + d * j

        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):
def calc(prepoint, nextpoint):
    return abs(nextpoint[0]-prepoint[0]) + abs(nextpoint[1]-prepoint[1])

def main():
    H,W,D = map(int,input().split())
    index  = [(0,0) for i in range(H*W+1)]
    A = []
    for i in range(H):
        temp = list(map(int, input().split()))
        for t in temp:
            index[t] = (i,temp.index(t))
        A.append(temp)
    Q = int(input())
    L_R_List = [list(map(int, input().split())) for i in range(Q)]

    dp = [0 for i in range(H*W+1)]
    for i in range(D, H*W+1):
        dp[i] = dp[i-D] + calc(index[i], index[i-D])
    for L_R in L_R_List:
        L = L_R[0]
        R = L_R[1]
        print(dp[R]-dp[L])

if __name__ == '__main__':
    main()

Solution (Python):
hwd = list(map(int, input().split()))
a = []
for i in range(hwd[0]):
    a.append(list(map(int, input().split())))
q = int(input())
lr = []
for i in range(q):
    lr.append(list(map(int, input().split())))

xy = [None] * hwd[0] * hwd[1]
for i in range(hwd[0]):
    for j in range(hwd[1]):
        xy[a[i][j] - 1] = [i, j]
        
power_accumulation = []
for i in range(hwd[2]):
    power = [0]
    number = 0
    place = i
    while place < hwd[0] * hwd[1] - hwd[2]:
        power.append(power[number] + abs(xy[place + hwd[2]][0] - xy[place][0]) + abs(xy[place + hwd[2]][1] - xy[place][1]))
        number = number + 1
        place = place + hwd[2]
    power_accumulation.append(power)

for i in range(q):
    test_power = power_accumulation[(lr[i][1] - 1) % hwd[2]][(lr[i][1] - 1) // hwd[2]] - power_accumulation[(lr[i][0]- 1) % hwd[2]][(lr[i][0] - 1) // hwd[2]]
    print(test_power)

Solution (Python):

H, W, D = list(map(int, input().split()))
A = {}
for y in range(H):
    tmp = list(map(int, input().split()))
    for x in range(W):
        A[tmp[x]] = (x+1, y+1)
Q = int(input())


d = [0 for _ in range(H*W)]
for i in range(1, D+1):
    x, y = A[i]

    j = i
    while j+D<=H*W:
        s, t = A[j+D]
        d[j+D-1] = d[j-1] + abs(x-s) + abs(y-t)
        x = s
        y = t
        j += D


for i in range(Q):
    L, R = list(map(int, input().split()))

    print(d[R-1] - d[L-1])

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

h,w,d=map(int,input().split())
table=[]
cost=[[0 for i in range(w)] for j in range(h)]
dic={}
for i in range(h):
    t=list(map(int,input().split()))
    table.append(t)
    for j in range(w):
        dic[t[j]]=(i,j)

for i in range(1,h*w+1):
    now=i
    a,b=dic[now]
    if cost[a][b]==0:
        while now<=h*w-d:
            now+=d
            y,x=dic[now]
            if cost[y][x]!=0:
                break
            cost[y][x]+=cost[a][b]+dist((a,b),(y,x))
            a,b=y,x

q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    a,b=dic[l]
    c,d=dic[r]
    print(cost[c][d]-cost[a][b])

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

comp = {}
for i in range(h):
    tmp = list(map(int, input().split(' ')))
    for j in range(w):
        comp[tmp[j]] = [i, j]

q = int(input())
lr = [map(int, input().split(' ')) for _ in range(q)]

dp = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
    cnt = dp[i - d]
    cnt += abs(comp[i][0] - comp[i - d][0])
    cnt += abs(comp[i][1] - comp[i - d][1])    
    dp[i] = cnt
    

for l, r in lr:
    print(dp[r] - dp[l])

Solution (Python):
line = input().split(" ")
a = list(map(int, line))
data = [0] * 90001
ans = 0
for i in range(0, a[0]):
    line = input().split(" ")
    temp = list(map(int, line))
    for j in range(0, a[1]):
        data[temp[j]] = [i, j]

memo = [0] * 90001

for i in range(1, a[0] * a[1]+1):
    if i < a[2]+1:
        memo[i] = 0
    else:
        memo[i] = memo[i - a[2]] + abs(data[i][0] - data[i - a[2]][0]) + abs(data[i][1] - data[i - a[2]][1])
times = int(input())
for i in range(0, times):
    line = list(map(int, input().split(" ")))
    print(memo[line[1]] - memo[line[0]])

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

Q = int(input())
L = [0 for _ in range(Q)]
R = [0 for _ in range(Q)]
for i in range(Q):
    L[i], R[i] = list(map(int, input().split()))

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

MP = [0 for _ in range(H*W)]
for i in range(H*W):
    if i < D:
        MP[i] = 0
    else:
        MP[i] = MP[i-D] + abs(masu[i][0]-masu[i-D][0]) + abs(masu[i][1]-masu[i-D][1])

for i in range(Q):
    print(MP[R[i]-1] - MP[L[i]-1])

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

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


def move_mp(pos1, pos2):
    return abs(pos1[0] - pos2[0]) + abs(pos1[1] - pos2[1])


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

for i in range(D + 1, H * W + 1):
    mp_list[i] = mp_list[i - D] + move_mp(Amap[i - D], Amap[i])

for i in range(Q):
    L, R = [int(x) for x in input().split()]

    print(mp_list[R] - mp_list[L])

Solution (Python):
H, W, D = list(map(int, input().split()))
 
dic = {}
for i in range(H):
    for j,v in enumerate(list(map(int, input().split()))):
        dic[v] = (i,j)
 
Q = int(input())
 
Qs = []
mi = 100000
ma = 1
for i in range(Q):
    l,r = list(map(int, input().split()))
    Qs.append((l,r))
    mi = min(mi, l)
    ma = max(ma, r)
 
S = [0 for i in range(100000)]
acm = 0
pi, pj = dic[mi]
for start in range(1, D+1):
    for i in range(start, ma+1, D):
        x,y = dic[i]
        acm += abs(x-pi) + abs(y-pj)
        S[i] = acm
        pi,pj = x,y

for i in Qs:
    l,r = i
    print(S[r] - S[l])

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

    pos = [0] * (H * W + 1)
    for i, row in enumerate(A):
        for j, value in enumerate(row):
            pos[value] = (i, j)

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

    for l, r in ST:
        print(d[r] - d[l])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())

H,W,D = Is()
d = dict()
for i in range(H):
    s = Is()
    for j,e in enumerate(s):
        d[e] = (i,j)
m = [0]*(H*W+1)
for i in range(D+1,H*W+1):
    m[i] = m[i-D] + abs(d[i-D][0] - d[i][0]) + abs(d[i-D][1] - d[i][1])

Q = I()
for q in range(Q):
    l,r = Is()
    print(m[r]-m[l])

Solution (Python):
h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
pos = {a[i][j]: (i,j) for i in range(h) for j in range(w)}
acc = [0]*(h*w+1)
for v in range(d+1, h*w+1):
    i, j = pos[v]
    x, y = pos[v-d]
    acc[v] = acc[v-d] + abs(x-i) + abs(y-j)
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(acc[r] - acc[l])

Solution (Python):
H, W, D = map(int, input().split())
A = [[int(i) for i in input().split()]for i in range(H)]
Q = int(input())
L = [0 for i in range(Q)]
R = [0 for i in range(Q)]
for i in range(Q):
    L[i], R[i] = map(int, input().split())
B = [(0,0) for i in range(H*W)]
for i in range(H):
    for j in range(W):
        B[A[i][j]-1] = (i,j)
C = [0 for i in range(H*W)]
for k in range(H*W):
    if k-D<0:
        C[k] = 0
    else:
        C[k] = C[k-D] + abs(B[k][0]-B[k-D][0])+abs(B[k][1]-B[k-D][1])
for n in range(Q):
    print(C[R[n]-1]-C[L[n]-1])

Solution (Python):
import numpy as np

H, W, D = [int(x) for x in input().strip().split(' ')]
stage = {}
for i in range(H):
    nums = [int(x) for x in input().strip().split(' ')]
    for j in range(W):
        stage[nums[j]] = [i + 1, j + 1]
Q = int(input())
tests = []
for _ in range(Q):
    tests.append([int(x) for x in input().strip().split(' ')])

scores = np.zeros([H * W + 1]).astype(np.int)
for i in range(H * W, 0, -1):
    if i + D > H * W:
        scores[i] = 0
    else:
        x, y = stage[i]
        ox, oy = stage[i + D]
        scores[i] = scores[i + D] + abs(x - ox) + abs(y - oy)

for i in range(Q):
    L, R = tests[i]
    print(scores[L] - scores[R])

Solution (Python):

def input_to_int_list(input_str):
    return list(map(lambda x: int(x), input_str.split(' ')))


h, w, d = input_to_int_list(input())
x_ix = [0 for _ in range(h * w + 1)] 
y_ix = [0 for _ in range(h * w + 1)] 

for i in range(h):
    input_list = input_to_int_list(input())
    for j in range(w):
        v = input_list[j]
        x_ix[v] = i 
        y_ix[v] = j 

cost_list = [0 for _ in range(h * w + 1)] 
for i in range(d + 1, h * w + 1): 
    cost_list[i] = cost_list[i - d] \
                    + abs(x_ix[i] - x_ix[i - d]) \
                    + abs(y_ix[i] - y_ix[i - d]) 

q = int(input())
for i in range(q):
    input_list = input_to_int_list(input())
    l = input_list[0]
    r = input_list[1]
    print(cost_list[r] - cost_list[l])

Solution (Python):
if __name__ == "__main__":
    H, W, D = list(map(int, (input().split(' '))))
    A = []
    for i in range(H):
        A.append(list(map(int, (input().split(' ')))))
    Q = int(input())
    LR = []
    for i in range(Q):
        LR.append(list(map(int, (input().split(' ')))))


















    dict_buf = {}




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

    d = {}
    for i in range(1, D+1):
        d[str(i)] = 0
    for i in range(D+1, H*W+1):
        d[str(i)] = d[str(i-D)] + \
                    abs(dict_buf[str(i)][0] - dict_buf[str(i-D)][0]) + \
                    abs(dict_buf[str(i)][1] - dict_buf[str(i-D)][1])

    for i in range(Q):














        print(d[str(LR[i][1])] - d[str(LR[i][0])])

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

coords = [[0,0] for x in range(H*W)]
for i in range(H):
    row = input().split()
    for j in range(W):
        coords[int(row[j]) - 1] = [i,j]

dp = [[] for x in range(D)]
for i in range(D):
    temp = i
    while temp < H*W:
        if temp == i:
            dp[i].append(0)
        else:
            a = len(dp[i])
            dp[i].append(dp[i][a - 1] + abs(coords[temp][0] - coords[temp - D][0]) + abs(coords[temp][1] - coords[temp - D][1]))
        temp += D

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

Solution (Python):
nTmp  = input().rstrip().split(' ')
nH = int(nTmp[0])
nW = int(nTmp[1])
nD = int(nTmp[2])

nS = nH * nW
Ans = 0

nDataH = [0 for i in range(nS + 1)]
nDataW = [0 for i in range(nS + 1)]

for i in range(nH):
    sTmp = input().rstrip().split(' ')
    
    for i2 in range(nW):
        nNum = int (sTmp[i2])
        nDataH[nNum] = i
        nDataW[nNum] = i2

nQ = int(input())

nDis = [0 for i in range(nS + 1)]

for i in range(nS + 1):
    nDis[i] = 0
    if i <= nD:
        continue
    
    nTmpDis = nDataH[i] - nDataH[i - nD] 
    if nTmpDis < 0:
        nTmpDis *= -1
    nDis[i] += nTmpDis
    nTmpDis = nDataW[i] - nDataW[i - nD] 
    if nTmpDis < 0:
        nTmpDis *= -1
    nDis[i] += nTmpDis
    nDis[i] += nDis[i - nD]

for i in range(nQ):
    sTmp = input().rstrip().split(' ')
    nL = int(sTmp[0])
    nR = int(sTmp[1])
    Ans = nDis[nR] - nDis[nL]
    print(Ans)

Solution (Python):
if __name__ == '__main__':
    h, w, d = map(int, input().split())
    f = [list(map(int, input().split())) for _ in range(h)]

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

    
    d_map = [0] * (h * w)
    for i in range(d, h * w):
        y, x = c_map[i]
        y2, x2 = c_map[i - d]
        d_map[i] = d_map[i - d] + abs(y2 - y) + abs(x2 - x)

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

    print("\n".join(map(str, results)))

Solution (Python):
h,w,d=map(int,input().split())
p=[0]*(h*w+d*2)
s=[0]*(h*w+d*2)
for x in range(h):
	y=1
	for a in map(int,input().split()):
		p[a]=[x,y]
		y+=1
for i in range(1,h*w+1-d):
	s[i+d]=s[i]+abs(p[i+d][0]-p[i][0])+abs(p[i+d][1]-p[i][1])
for i in range(int(input())):
	l,r=map(int,input().split())
	print(s[r]-s[l])

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

for i in range(H):
    row = list(map(int, input().split()))
    for j, value in enumerate(row):
        position[value] = (i, j)

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

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

Solution (Python):
H, W, D = map(int, input().split())
pos = [None]*(H*W)

for i in range(H):
    row = list(map(int, input().split()))
    for j in range(W):
        pos[row[j]-1] = (i, j)

costs = [0]*(H*W)
for i in range(1, D+1):
    current = i + D
    while current <= H*W:
        costs[current - 1] = costs[current - 1 - D] + abs(pos[current - 1][0] - pos[current - 1 - D][0]) + abs(pos[current - 1][1] - pos[current - 1 - D][1])
        current += D

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

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

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

dt = [0] * (H * W + 1)
for x in range(D + 1, H * W + 1):
    y = x - D
    p1, p2 = pos[x], 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):

"""
D - Practical Skill Test
https://beta.atcoder.jp/contests/abc089/tasks/abc089_d

"""
import sys
from sys import stdin
input = stdin.readline


def sub_solve(l, r):
    sx, sy = numbers[l]
    gx, gy = numbers[r]
    return abs(sx - gx) + abs(sy - gy)


def solve(queries, H, W, D):
    dp = [0] * (H*W+1)
    for i in range(D+1, H*W+1):
        dp[i] = dp[i-D] + sub_solve(i-D, i)

    for l, r in queries:
        ans = dp[r] - dp[l]
        print(ans)


numbers = dict()
def main(args):
    global numbers
    H, W, D = map(int, input().split())

    for y in range(1, H+1):
        tmp = [int(x) for x in input().split()]
        for x, i in enumerate(tmp, start=1):
            numbers[i] = (x, y)

    Q = int(input())
    queries = []
    for _ in range(Q):
        queries.append([int(x) for x in input().split()])

    solve(queries, H, W, D)


if __name__ == '__main__':
    main(sys.argv[1:])

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):
import sys
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

dp = {}

def dp_search(L, R, D, num_dic):
    global dp
    if (L, R) in dp:
        return dp[(L, R)]
    if L== R:
        return 0

    if L + D == R:
        now_pos = num_dic[L]
        next_pos = num_dic[R]
        dp[(L, R)] =  abs(next_pos[0] - now_pos[0]) + abs(next_pos[1] - now_pos[1])
        return dp[(L, R)]

    dp[(L, R)] = dp_search(L , R - D, D , num_dic) + dp_search(L + D , R, D , num_dic)

    return dp[(L, R)]


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W, D] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    num_dic= {}
    for i in range(H):
        input_raw = read_func().strip().split()
        for j in range(W):
            num_dic[int(input_raw[j])] = (i, j)
    input_raw = read_func().strip().split()
    [Q] = [int(input_raw[0])]
    test_list = []
    for i in range(Q):
        input_raw = read_func().strip().split()
        test_list.append((int(input_raw[0]), int(input_raw[1])))

    dp = [[] for i in range(D)]

    for i in range(0, H * W):
        A = i + 1
        if len(dp[A % (D)]) == 0:
            dp[A % (D)].append((A, 0))
        else:
            (prev_point, prev_cost)= dp[A % D][len(dp[A % D]) - 1]
            prev_pos = num_dic[prev_point]
            now_pos = num_dic[A]
            dp[A % (D)].append((A, prev_cost +abs(prev_pos[0] - now_pos[0]) + abs(prev_pos[1] - now_pos[1])))

    for test in test_list:
        L = test[0]
        R = test[1]
        if L==R:
            print 0
        else:
            print (dp[L % (D)] [R/(D) - 1 + (1 if R % D != 0 else 0)][1] -
                    (dp[L % (D)] [L/(D) - 1 + (1 if L % D != 0 else 0)][1] ))




if __name__ == '__main__':
    main()