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 sys
input = sys.stdin.readline

def main():
    H, W, D = map(int, input().split())
    A = list(list(map(int, input().split())) for _ in range(H))
    Q = int(input())
    B = [(0,0)] * (H * W + 5)
    for h in range(H):
        for w in range(W): 
            B[A[h][w]] = (h+1, w+1)


    C = [0] * (H * W + 5)
    for i in range(H * W + 1):
        if i // D == 0:
            continue
        tmp = abs(B[i][0] - B[i-D][0]) + abs(B[i][1] - B[i-D][1]) 
        C[i] = tmp + C[i - D]

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


if __name__ == "__main__":
    main()

Solution (Python):


import sys

H, W, D = map(int, sys.stdin.buffer.readline().split())
A = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(H)]

place = [-1] * (H*W + 1)
for row in range(H):
    for col in range(W):
        place[A[row][col]] = (row, col)

cum_cost = [[0] for _ in range(D+1)]
for i in range(1, D+1):
    x = i
    y = x + D
    while y <= H*W:
        cum_cost[i].append(cum_cost[i][-1] + abs(place[x][0] - place[y][0]) + abs(place[x][1] - place[y][1]))
        x += D
        y += D

Q = int(sys.stdin.buffer.readline())

for _ in range(Q):
    L, R = map(int, sys.stdin.buffer.readline().split())
    ans = 0
    tmp = L % D
    if tmp == 0:
        print(cum_cost[-1][R // D - 1] - cum_cost[-1][L // D - 1])
    else:
        print(cum_cost[tmp][R // D] - cum_cost[tmp][L // D])

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

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

for y in range(h):
    line = list(map(int,input().split()))
    for x in range(w):
        num = line[x]
        dic[num] = (x,y)

com_sum = [0]*(h*w + 1)

for n in range(1,d+1):
    com_sum[n] = 0
    while n+d <= h*w:
        nx,ny = dic[n+d]
        x,y = dic[n]
        com_sum[n+d] = com_sum[n] + abs(nx-x) + abs(ny-y)
        n += d
    
Q = int(input())
for q in range(Q):
    l,r = map(int,input().split())
    print(com_sum[r] - com_sum[l])

Solution (Python):

import sys


def solve(H: int, W: int, D: int, A: "List[List[int]]", Q: int, L: "List[int]", R: "List[int]"):
    N = H*W

    
    matrix = [()]*(N+1)
    for h in range(H):
        for w in range(W):
            matrix[A[h][w]] = (h,w)
    
    def get_distance(start: int, end: int) -> int:
        start_x = matrix[start][0]
        start_y = matrix[start][1]
        end_x = matrix[end][0]
        end_y = matrix[end][1]
        return abs(start_x-end_x)+abs(start_y-end_y)

    distance = []

    for start in range(1,D+1):
        end = start
        
        distance_matrix = {}
        while end <= N:
            distance_matrix[end] = 0
            end += D

        end = start
        prev_end = end

        while end <= N:
            distance_matrix[end] = distance_matrix[prev_end]+ get_distance(prev_end,end)
            prev_end = end
            end += D
        
        distance.append(distance_matrix)
    
    for i in range(Q):
        s = L[i]%D
        if s == 0:
            s = D
        distance_matrix = distance[s-1]
        d = distance_matrix[R[i]]-distance_matrix[L[i]]
        print(d)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    W = int(next(tokens))  
    D = int(next(tokens))  
    A = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  
    Q = int(next(tokens))  
    L = [int()] * (Q)  
    R = [int()] * (Q)  
    for i in range(Q):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    solve(H, W, D, A, Q, L, R)

if __name__ == '__main__':
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W, D = MAP()
A = [LIST() for _ in range(H)]

Q = INT()
LR = [LIST() for _ in range(Q)]

dic = [[] for _ in range(D)]

for i in range(H):
	for j in range(W):
		dic[A[i][j]%D].append([A[i][j], i, j])

for lis in dic:
	lis.sort(key=lambda x:x[0])

for lis in dic:
	lis[0][0] = 0
	for i in range(len(lis)):
		if i == len(lis)-1:
			break
		point = (lis[i][1], lis[i][2])
		dist_point = (lis[i+1][1], lis[i+1][2])
		lis[i+1][0] = lis[i][0] + abs(point[0]-dist_point[0]) + abs(point[1]-dist_point[1])

for L, R in LR:
	print(dic[R%D][ceil(R/D)-1][0]-dic[R%D][ceil(L/D)-1][0])

Solution (Python):
h,w,d=map(int,input().split())
field=[[]]*(h*w)
for i in range(h):
	x=list(map(int,input().split()))
	for j in range(w):
		field[x[j]-1]=[i,j]
dis=[10**20]*(h*w)
for i in range(d):
	dis[i]=0
for i in range((h*w)):
	if i>=d:
		dis[i]=dis[i-d]+abs(field[i][0]-field[i-d][0])\
		+abs(field[i][1]-field[i-d][1])
q=int(input())
for i in range(q):
	l,r=map(int,input().split())
	print(dis[r-1]-dis[l-1])

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

al_l = []
for _ in range(h):
    al = list(map(int,input().split()))
    al_l.append(al)

from collections import defaultdict
dic = {}
for i in range(h):
    for j in range(w):
        dic[al_l[i][j]] = (i,j)

path = {}
for i in range(1,d+1):
    tmp = 0
    while True:
        path[i] = tmp
        i += d
        if i > h*w:
            break
        x1, y1 = dic[i]
        x2, y2 = dic[i-d]
        tmp += abs(x1-x2) + abs(y2-y1)

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

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_list = [[0] * 2 for _ in range(H*W+1)]
for h in range(H):
    for w in range(W):
        number_list[A[h][w]] = [h, w]

d = [0] * (H*W+1)
for idx in range(H*W+1):
    pre_idx = idx - D
    if pre_idx <= 0:
        continue
    diff = abs(number_list[idx][0] - number_list[pre_idx][0])
    diff += abs(number_list[idx][1] - number_list[pre_idx][1])
    d[idx] = d[pre_idx] + diff

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

Solution (Python):
h,w,d=map(int,input().split())
field=[[]]*(h*w)
for i in range(h):
	x=list(map(int,input().split()))
	for j in range(w):
		field[x[j]-1]=[i,j]
dis=[10**20]*(h*w)
for i in range(d):
	dis[i]=0
for i in range((h*w)):
	if i>=d:
		dis[i]=dis[i-d]+abs(field[i][0]-field[i-d][0])\
		+abs(field[i][1]-field[i-d][1])
q=int(input())
for i in range(q):
	l,r=map(int,input().split())
	print(dis[r-1]-dis[l-1])

Solution (Python):
h,w,d=map(int,input().split())
l=[]
for i in range(h):
    l.append(list(map(int,input().split())))
px=[0]*(h*w)
py=[0]*(h*w)
ans=[0]*(h*w)
for i in range(h):
    for j in range(w):
        px[l[i][j]-1]=j
        py[l[i][j]-1]=i
for i in range(d,h*w):
    ans[i]=ans[i-d]+abs(px[i]-px[i-d])+abs(py[i]-py[i-d])
q=int(input())
for i in range(q):
    a,b=map(int,input().split())
    print(ans[b-1]-ans[a-1])

Solution (Python):
H,W,D=map(int,input().split())
import collections
import bisect
table=collections.defaultdict(list)
table2=collections.defaultdict(list)
dp=collections.defaultdict(list)
field=[list(map(int,input().split())) for i in range(H)]
for i in range(H):
  for j in range(W):
    table[field[i][j]%D].append((field[i][j],i,j))
    table2[field[i][j]%D].append(field[i][j])
for x in table:
  table[x].sort(key=lambda x:x[0])
  dp[x]=[0]*len(table[x])
  for i in range(1,len(table[x])):
    dp[x][i]=dp[x][i-1]+abs(table[x][i][1]-table[x][i-1][1])+abs(table[x][i][2]-table[x][i-1][2])
  table2[x].sort()
Q=int(input())
LR=[list(map(int,input().split())) for i in range(Q)]
for i in range(Q):
  ans=0
  x,y = LR[i]
  
  id = bisect.bisect_left(table2[x%D],x)
  id2=bisect.bisect_left(table2[x%D],y)
  print(dp[x%D][id2]-dp[x%D][id])

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    h,w,d=map(int,input().split())
    grid=[]
    cnt=0
    for i in range(h):
        for j,a in enumerate(map(int,input().split())):
            a-=1
            grid.append((a,(i,j)))
    grid.sort()

    n=h*w
    A=list(map(lambda x:x[1],grid))
    C=[0]*n
    for r in range(d):
        for x in range(r,n-d,d):
            C[x+d]=C[x]+abs(A[x+d][0]-A[x][0])+abs(A[x+d][1]-A[x][1])

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

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

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

cost = [[0 for _ in range((H * W) // D + 1)] for _ in range(D)]
for i in range(H * W):
  d, m = divmod(i, D)
  if d > 0:
    cost[m][d] = cost[m][d - 1] + abs(li[i][0] - li[i - D][0]) + abs(li[i][1] - li[i - D][1]) 



for l, r in LR:
  print(cost[(l - 1) % D][(r - 1) // D] - cost[(l - 1) % D][(l - 1) // D])

Solution (Python):
H, W, D = map(int, input().split())
X = [(0, 0) for _ in range(H*W)]
Y = [0] * (H*W)
for i in range(H):
    A = [int(a) - 1 for a in input().split()]
    for j in range(W):
        X[A[j]] = (i, j)
for i in range(H*W - D):
    Y[i+D] = Y[i] + abs(X[i+D][0] - X[i][0]) + abs(X[i+D][1] - X[i][1])
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(Y[r-1] - Y[l-1])

Solution (Python):

h, w, d = map(int, input().split())
x = [None] * h * w
y = [[0] for _ in range(d)]
for i in range(h):
    r = [int(x) for x in input().split()]
    for j in range(w):
        x[r[j] - 1] = (i, j)
for i in range(d):
    for j in range(i + d, h * w, d):
        y[i].append(abs(x[j][0] - x[j - d][0]) + abs(x[j][1] - x[j - d][1]))
        y[i][-1] += y[i][-2]
for _ in range(int(input())):
    l, r = [int(x) - 1 for x in input().split()]
    m = l % d
    print(y[m][r // d] - y[m][l // d])

Solution (Python):

h,w,d=map(int,input().split())
lists=[0 for j in range(h)]
for j in range(h):
    lis=list(map(int,input().split()))
    lists[j]=lis
uselist=[0 for i in range(h*w)]
for i in range(h):
    for j in range(w):
        uselist[lists[i][j]-1]=(i+1,j+1)

distance=[[0]for i in range(d)]
for i in range(1,d+1):
    start=i
    nums=0
    
    while start<=h*w-d:
        a=abs(uselist[start+d-1][0]-uselist[start-1][0])+abs(uselist[start+d-1][1]-uselist[start-1][1])
        nums=nums+a
        distance[i-1].append(nums)
        start+=d

q=int(input())
for k in range(q):
    s,g=map(int,input().split())
    if s%d!=0:
      mod=s%d-1
    elif s%d==0:
      mod=d-1
    print(distance[mod][(g-1-mod)//d]-distance[mod][(s-1-mod)//d])

Solution (Python):
h, w, d = map(int, input().split())
cell = {}
for i in range(h):
  row = list(map(int, input().split()))
  for j, a in enumerate(row):
    cell[a] = (i, j)

max_point = h * w
req_mp = [0 for i in range(max_point)]
for i in range(max_point):
  if i < d:
    req_mp[i] = 0
  else:
    temp = req_mp[i-d]
    temp += abs(cell[i-d+1][0] - cell[i+1][0])
    temp += abs(cell[i-d+1][1] - cell[i+1][1])
    req_mp[i] = temp

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

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1

def main():
    h, w, d = map(int, input().split())
    atoij = [[] for _ in range(h * w)]
    for i in range(h):
        for j, a in enumerate(map(int, input().split())):
            a -= 1
            atoij[a] = [i, j]
    
    q = int(input())
    ans=[0]*q
    mx = [0] * d
    mn = [100000] * d
    qq = [[] for _ in range(d)]
    for qi in range(q):
        l, r = map(int1, input().split())
        md = l % d
        if l < mn[md]: mn[md] = l
        if r > mx[md]: mx[md] = r
        qq[md].append([qi, l, r])
    for md in range(d):
        if not qq[md]: continue
        a = mn[md]
        ed = mx[md]
        s = 0
        dist = {}
        i0, j0 = atoij[a]
        while a <= ed:
            i1, j1 = atoij[a]
            s += abs(i0 - i1) + abs(j0 - j1)
            dist[a] = s
            i0, j0 = i1, j1
            a += d
        for qi, l, r in qq[md]:
            ans[qi]=dist[r]-dist[l]
    for x in ans:
        print(x)

main()

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


def main():
    H, W, D = map(int, input().split())
    d = [0]*(H*W)
    for h in range(H):
        a = list(map(int, input().split()))
        for i, x in enumerate(a):
            d[x-1] = h*W + i

    mp = [0]*(H*W)
    for i in range(D, H*W):
        mp[i] = mp[i-D] + abs(d[i]//W - d[i-D]//W) + abs(d[i]%W - d[i-D]%W)

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


if __name__ == '__main__':
    main()

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


def main():
    H, W, D = map(int, input().split())
    A = []
    d = [0]*(H*W)
    for h in range(H):
        a = list(map(int, input().split()))
        A.append(a)
        for i, x in enumerate(a):
            d[x-1] = h*W + i
    mp = [0]*(H*W)
    for i in range(H*W):
        if i >= D:
            mp[i] = mp[i-D] + abs(d[i]//W - d[i-D]//W) + abs(d[i]%W - d[i-D]%W)
    Q = int(input())
    for q in range(Q):
        ans = 0
        l, r = map(int, input().split())
        print(mp[r-1] - mp[l-1])


if __name__ == '__main__':
    main()

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

L=[[0]*(H*W//D+(H*W%D>=i)) for i in range(1,D+1)]
for i in range(D,H*W):
  n=i+1
  L[n%D-1][(n-1)//D]=L[n%D-1][(n-1)//D-1]+abs(A[i][1]-A[i-D][1])+abs(A[i][0]-A[i-D][0])

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

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

dx = [0 for _ in range(h*w+5)]
dy = [0 for _ in range(h*w+5)]

for i in range(h):
    for j in range(w):
        dx[a[i][j]] = i
        dy[a[i][j]] = j

dfromd = [0 for _ in range(h*w+1)]

for i in range(d+1,h*w+1):
        dfromd[i] = dfromd[i-d]+abs(dx[i-d]-dx[i])+abs(dy[i-d]-dy[i])

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

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


def main():

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

    a = [(0, (0, 0))]
    for i in range(H):
        a.extend([(element, [i, w]) for w, element in enumerate(A[i])])

    a.sort()
    tmp, number = zip(*a)
    number = np.array(number)
    x = np.resize(number[:, 0], (H * W // D + 1, D))
    y = np.resize(number[:, 1], (H * W // D + 1, D))

    magic = np.abs(x[1:] - x[:-1]) + np.abs(y[1:] - y[:-1])
    np.cumsum(magic, axis=0, out=magic)

    for L, R in zip(LR, LR):
        if L != R:
            q1 = R // D - 1
            q2 = L // D - 1
            r = R % D
            if q2 == -1:
                print(magic[q1][r])
            else:
                print(magic[q1][r] - magic[q2][r])
        else:
            print(0)


if __name__ == '__main__':
    main()

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

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

a = [(0, (0, 0))]
for i in range(H):
    a.extend([(element, [i, w]) for w, element in enumerate(A[i])])

a.sort()
tmp, number = zip(*a)
number = np.array(number)
x = np.resize(number[:, 0], (H * W // D + 1, D))
y = np.resize(number[:, 1], (H * W // D + 1, D))

magic = np.abs(x[1:] - x[:-1]) + np.abs(y[1:] - y[:-1])
np.cumsum(magic, axis=0, out=magic)

for L, R in zip(LR, LR):
    if L != R:
        q1 = R // D - 1
        q2 = L // D - 1
        r = R % D
        if q2 == -1:
            print(magic[q1][r])
        else:
            print(magic[q1][r] - magic[q2][r])
    else:
        print(0)

Solution (Python):
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

H, W, D = LI()
data = H*W
cur = int(0)
A = [LI() for _ in range(H)]
ALocat = [None]*(data+1)
a = -1
for i in A:
    a +=1
    b = 0
    for j in i:
        ALocat[j] = [a, b]
        b +=1


ALocat[0] = [0,0]
movecost = [0]*(data+1)
for i in range(D,data+1):
    movecost[i] = movecost[i-D] + abs(ALocat[i][0]-ALocat[i-D][0])\
                                + abs(ALocat[i][1]-ALocat[i-D][1])


ans = []
Q = I()
for _ in range(Q):
    L, R = LI()
    cur = movecost[R]-movecost[L]
    ans.append(cur)
for v in ans:
    print(v)

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-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)]
li=[[] for i in range(d)]
for i in range(h):
    for j in range(w):
        li[a[i][j]%d].append([a[i][j],i,j])

for i in range(d):
    li[i].sort()


c=[[0]*(len(li[i])+1) for i in range(d)]

for i in range(d):
    for j in range(1,len(li[i])):
        c[i][j+1]=c[i][j]+abs(li[i][j-1][1]-li[i][j][1])+abs(li[i][j-1][2]-li[i][j][2])


for i in range(q):
    ama=lr[i][0]%d
    print(c[ama][(lr[i][1]+d-1)//d]-c[ama][(lr[i][0]+d-1)//d])

Solution (Python):
H,W,D = map(int,input().split())
A = []
for j in range(H):
  for i, a in enumerate(map(int,input().split())):
    A.append([a,i,j])
A.sort()
lenA = len(A)

points = [0] * lenA
for inia in [i for i in range(D)]:
  i = inia + D
  while i < lenA:
    points[i] = points[i-D] + abs(A[i][1]-A[i-D][1]) + abs(A[i][2]-A[i-D][2])
    i += D

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

Solution (Python):
from sys import stdin
H,W,D = [int(x) for x in stdin.readline().rstrip().split()]
data = [0]*(H*W+1)
for i in range(H):
    for j,A in enumerate([int(x) for x in stdin.readline().rstrip().split()]):
        data[A] = (i,j)
dp = [0]*(H*W+1)
for j in range(H*W+1):
    if j > D:
        dp[j] = dp[j-D] + abs(data[j][0]-data[j-D][0]) + abs(data[j][1]-data[j-D][1])
Q = int(stdin.readline().rstrip())
for _ in range(Q):
    L,R = [int(x) for x in stdin.readline().rstrip().split()]
    print(dp[R]-dp[L])

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)]
data=[[[0,0]]*(h*w//d+1) for i in range(d)]
for i in range(h):
    for j in range(w):
        b=a[i][j]%d
        c=a[i][j]//d
        data[b][c]=[i, j]
lst=[[0]*(h*w//d+1) for i in range(d)]
for i in range(d):
    for j in range(1,h*w//d+1):
        x,y=data[i][j]
        X,Y=data[i][j-1]
        lst[i][j]=lst[i][j-1]+abs(x-X)+abs(y-Y)
for u in lr:
    l,r=u
    b=l%d
    c=l//d
    e=r//d
    ans=lst[b][e]-lst[b][c]
    print(ans)

Solution (Python):
import sys
import bisect
h, w, d = [int(i) for i in sys.stdin.readline().split()]
a_ls = []
for y in range(h):
    a = [int(i) for i in sys.stdin.readline().split()]
    for x in range(w):
        a_ls += [(a[x], x, y)]

a_ls.sort(key=lambda x:x[0])
diff_ls = []
for ind in range(h*w):
    if ind < d:
        diff_ls.append(0)
    else:
        start = a_ls[ind-d]
        goal = a_ls[ind]
        diff = diff_ls[ind-d] + abs(start[2] - goal[2]) + abs(start[1] - goal[1])
        diff_ls.append(diff)
q = int(input())
for j in range(q):
    l, r = [int(i) for i in sys.stdin.readline().split()]
    l -= 1
    r -= 1
    print(diff_ls[r] - diff_ls[l])

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

for i in range(1,H+1):
    Ai=list(map(int,input().split()))
    for j,Aij in enumerate(Ai):
        l[Aij%D].append((Aij,i,j+1))

for lr in l:
    lr.sort()



d=[]
for r in range(D):
    lr=[]
    for i in range(len(l[r])-1):
        lr.append(abs(l[r][i][1]-l[r][i+1][1])+abs(l[r][i][2]-l[r][i+1][2]))
    d.append(lr)



s=[]
for r in range(D):
    sr=[0]
    for i in range(len(d[r])):
        sr.append(sr[i]+d[r][i])
    s.append(sr)



Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    r=L%D
    left=(L-r)//D-(1 if r==0 else 0)
    right=(R-r)//D-(1 if r==0 else 0)

    print(s[r][right]-s[r][left])

Solution (Python):
h,w,d = map(int,input().split())
arr = []
for i in range(h):
    tmp_list = list(map(int,input().split()))
    arr.append(tmp_list)
q = int(input())
querry = []
for i in range(q):
    querry.append(list(map(int,input().split())))
num_list = [[0]*2 for i in range(h*w + 1)]
for i in range(h):
    for j in range(w):
        num_list[arr[i][j]] = [i,j]
cost_list = [0]*(h*w + 1)
for i in range(1,h*w):
    for r in range(h*w):
        if i > h*w - d:
            break
        if cost_list[i + d] == 0:
            x0 = num_list[i][0]
            x1 = num_list[i + d][0]
            y0 = num_list[i][1]
            y1 = num_list[i + d][1]
            cost_list[i + d] += cost_list[i] + abs(x0-x1) +  abs(y0-y1)
        else:
            break
        i += d
for l,r in querry:
    print(cost_list[r] - cost_list[l])

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

L = [0]*(H*W+1)
for i in range(H):
    for j in range(W):
        L[A[i][j]] = [i, j]
        
E = [0]*(H*W+1)
for i in range(D+1, H*W+1):
    E[i] = E[i-D] + abs(L[i][0]-L[i-D][0])+abs(L[i][1]-L[i-D][1])
    
for i in range(Q):
    ans = 0
    l, r = map(int, input().split())
    ans = E[r] - E[l]
    print(ans)

Solution (Python):
h,w,d=map(int,input().split())
e={}
ans=[0]*(h*w+1)
for i in range(1,h+1):
    a=list(map(int,input().split()))
    for j in range(w):
        e[a[j]]=(i,j+1)
for i in range(d+1,h*w+1):
    x,y=e[i]
    c,v=e[i-d]
    ans[i]=abs(x-c)+abs(y-v)+ans[i-d]

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

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









def main():
    h,w,D=map(int,input().split())
    li=[0]*(h*w+1)
    kyori=[0]*(h*w+1)
    for i in range(h):
        A=list(map(int,input().split()))
        for j in range(w):
            li[A[j]]=(i+1,j+1)

    for i in range(D+1,h*w+1):
        kyori[i]=kyori[i-D]+abs(li[i][0]-li[i-D][0])+abs(li[i][1]-li[i-D][1])

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


if __name__ == '__main__':
    main()

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









def main():
    h,w,D=map(int,input().split())
    li=[0]*(h*w+1)
    kyori=[0]*(h*w+1)
    for i in range(h):
        A=list(map(int,input().split()))
        for j in range(w):
            li[A[j]]=(i+1,j+1)

    for i in range(D+1,h*w+1):
        kyori[i]=kyori[i-D]+abs(li[i][0]-li[i-D][0])+abs(li[i][1]-li[i-D][1])

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


if __name__ == '__main__':
    main()

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

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

dic = {}
K = H*W//D
memo = [[0]* (K+1) for _ in range(D+1)]

for y in range(1, H+1):
    A = list(map(int, input().split()))
    for x, a in enumerate(A, 1):
        dic[a] = [x, y]

for extra in range(H*W+1, H*W+2*D):
    dic[extra] = [0, 0]

for i in range(1, D+1):
    for j in range(K):
        x, y = dic[i+D*j]
        nx, ny = dic[i+D*(j+1)]
        cost = abs(x-nx) + abs(y-ny)
        memo[i][j+1] = memo[i][j] + cost

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    i = L % D
    j = L//D
    delta = (R-L)//D
    if i == 0:
        i = D
        j -= 1
    ans = memo[i][j+delta] - memo[i][j]
    print(ans)

Solution (Python):
def dist(x,y):
    return abs(x[0]-y[0])+abs(x[1]-y[1])
H,W,D = map(int,input().split())
G = {}
for i in range(H):
    row = list(map(int,input().split()))
    for j in range(W):
        G[row[j]]=(i,j)
B = {i:0 for i in range(1,D+1)}
for i in range(1,D+1):
    for j in range(i+D,H*W+1,D):
        B[j] = B[j-D]+dist(G[j-D],G[j])
Q = int(input())
for _ in range(Q):
    L,R = map(int,input().split())
    print(B[R]-B[L])

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


HWdict = {}
for j in range(0, H):
    for k in range(0,W):
        HWdict[l1[j][k]] = [j, k]


mylist = []
for i in range(0,D):
    mylist.append({})

for i in range(0, D):
    j = 1
    mylist[i][i+1] = 0
    while ((i+1) + j*D) <= H*W:
        mylist[i][(i+1) + j*D] = mylist[i][(i+1)+ (j-1)*D] + abs(HWdict[(i+1) + j*D][0]- HWdict[(i+1) + (j-1)* D][0]) + abs(HWdict[(i+1) + j*D][1] - HWdict[(i+1) + (j-1)* D][1])
        j += 1

L = 0
R = 0
ans = 0
for i in range(0, Q):
    L = l2[i][0]
    R = l2[i][1]
    print(mylist[R%D-1][R] - mylist[R%D-1][L])

Solution (Python):
import sys
import itertools
from itertools import accumulate
def main():
    input = sys.stdin.readline
    def inputs():return [int(x) for x in input().split()]
    H,W,D = inputs()
    w = [[None]*W for i in range(H)]
    A = []
    for i in  range(H):
        B = inputs()
        A.append(B)
    E={i:[] for i in range(1,H*W+1)}
    for i in range(H):
        for j in range(W):
            a = A[i][j]
            if a<=H*W:
                E[a].append((i+1,j+1))
    
    dis = [0]*(H*W+1)
    for i in range(1,H*W+1):
        if i+D<=H*W:
            
            x = E[i][0][0]
            y = E[i][0][1]
            a = E[i+D][0][0]
            b = E[i+D][0][1]
            dis[i+D] = dis[i]+abs(a-x)+abs(b-y)
    Q = int(input())
    for i in range(Q):
        r,l = inputs()
        print(dis[l]-dis[r])
main()

Solution (Python):
H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for i in range(H)]
Q = int(input())
S = [list(map(int,input().split())) for i in range(Q)]
P = [None]*(H*W+1)
for i in range(H):
    for j in range(W):
        P[A[i][j]] = [i,j]

Accum = [0]*(H*W+1)
accum = 0

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

for s in S:
    print(Accum[s[1]]-Accum[s[0]])

Solution (Python):
H,W,D = map(int,input().split())
Point = {}
for y in range(H) :
    line = list(map(int,input().split()))
    for x,p in enumerate(line) :
        Point[p] = (y,x)

Q = int(input())

def dist(ny,nx,py,px) :
    return abs(ny-py) + abs(nx-px)

Cost = [0]*(H*W+1)
for i in range(D+1, H*W+1) :
    yi,xi = Point[i-D]
    yj,xj = Point[i]
    Cost[i] = Cost[i-D] + dist(yi,xi,yj,xj)


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

Solution (Python):
H,W,D = map(int,input().split())
Point = {}
for y in range(H) :
    line = list(map(int,input().split()))
    for x,p in enumerate(line) :
        Point[p] = (y,x)

Q = int(input())

def dist(ny,nx,py,px) :
    return abs(ny-py) + abs(nx-px)

Cost = [0]*(H*W+1)
for i in range(D+1, H*W+1) :
    yi,xi = Point[i-D]
    yj,xj = Point[i]
    Cost[i] = Cost[i-D] + dist(yi,xi,yj,xj)


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

Solution (Python):
import sys
input = sys.stdin.readline
h, w, d = map(int, input().split())
a = {}
l = list(range(1, h * w + 1))
for i in range(h):
  for j, x in enumerate(input().split()):
    a[int(x)] = (i, j)
memo = {}
def calc(s):
  tmp = 0
  memo[a[s+1]] = 0
  for Xc, Xn in zip(l[s::d], l[s+d::d]):
    xc, yc = a[Xc]
    xn, yn = a[Xn]
    tmp += abs(xc - xn) + abs(yc - yn)
    memo[a[Xn]] = tmp
for i in range(d):
  calc(i)
for _ in range(int(input())):
  l, r = map(int, input().split())
  print(memo[a[r]] - memo[a[l]])

Solution (Python):
H, W, D = map(int, input().split())
Board = [0] * (H*W+1)
path = [[0] for _ in range(D)] 
for h in range(H):
    A = list(map(int, input().split()))
    for w in range(W):
        Board[A[w]] = [w+1, h+1]
for i in range(1, D+1):
    d = i % D
    for j in range(i+D, H*W+1, D):
        path[d].append(path[d][(j+(D-1))//D-2] + abs(Board[j][0] - Board[j-D][0]) + abs(Board[j][1] - Board[j-D][1]))

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