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
from itertools import accumulate

input = sys.stdin.readline


def solve(H, W, D, A, Q, LR):
    position = [None] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

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

    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i + D] = abs(x - w) + abs(y - h)

    for d in range(1, D + 1):
        mp[d::D] = list(accumulate(mp[d::D]))

    ans = [mp[r] - mp[l] for l, r in LR]
    ans = "\n".join(map(str, ans))
    return ans


def main():
    H, W, D = map(int, input().split())
    A = [None] * H
    for i in range(H):
        A[i] = tuple(map(int, input().split()))
    Q = int(input())
    LR = [None] * Q
    for i in range(Q):
        LR[i] = tuple(map(int, input().split()))

    ans = solve(H, W, D, A, Q, LR)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from itertools import accumulate

input = sys.stdin.readline


def dfs(H, W, D, A, Q, LR):
    position = [(-1, -1)] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

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

    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i + D] = abs(x - w) + abs(y - h)

    for d in range(1, D + 1):
        mp[d::D] = list(accumulate(mp[d::D]))

    ans = [mp[r] - mp[l] for l, r in LR]
    return ans


def main():
    H, W, D = map(int, input().split())
    A = [None] * H
    for i in range(H):
        A[i] = tuple(map(int, input().split()))
    Q = int(input())
    LR = [None] * Q
    for i in range(Q):
        LR[i] = tuple(map(int, input().split()))

    ans = [0] * Q
    ans = dfs(H, W, D, A, Q, LR)

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys

import numpy as np

input = sys.stdin.readline


def dfs(H, W, D, A, Q, LR, ans):
    position = [(-1, -1)] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

    mp = np.zeros(shape=(H * W + 1), dtype=np.int64)

    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i + D] = abs(x - w) + abs(y - h)

    for d in range(1, D + 1):
        mp[d::D] = np.cumsum(mp[d::D])

    for i in range(Q):
        l, r = LR[i]
        ans[i] = mp[r] - mp[l]


def main():
    H, W, D = map(int, input().split())
    A = np.zeros(shape=(H, W), dtype=np.int64)
    for i in range(H):
        A[i] = tuple(map(int, input().split()))
    Q = int(input())
    LR = np.zeros(shape=(Q, 2), dtype=np.int64)
    for i in range(Q):
        LR[i] = tuple(map(int, input().split()))

    ans = np.zeros(shape=Q, dtype=np.int64)
    dfs(H, W, D, A, Q, LR, ans)

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("void(i8,i8,i8,i8[:,:],i8,i8[:,:],i8[:])", cache=True)
def dfs(H, W, D, A, Q, LR, ans):
    position = [(-1, -1)] * (H * W + 1)
    for h in range(H):
        for w in range(W):
            position[A[h][w]] = (h, w)

    mp = np.zeros(shape=(H * W + 1), dtype=np.int64)

    for i in range(1, H * W + 1 - D):
        h, w = position[i]
        y, x = position[i + D]
        mp[i + D] = abs(x - w) + abs(y - h)

    for d in range(1, D + 1):
        mp[d::D] = np.cumsum(mp[d::D])

    for i in range(Q):
        l, r = LR[i]
        ans[i] = mp[r] - mp[l]


def main():
    H, W, D = map(int, input().split())
    A = np.zeros(shape=(H, W), dtype=np.int64)
    for i in range(H):
        A[i] = tuple(map(int, input().split()))
    Q = int(input())
    LR = np.zeros(shape=(Q, 2), dtype=np.int64)
    for i in range(Q):
        LR[i] = tuple(map(int, input().split()))

    ans = np.zeros(shape=Q, dtype=np.int64)
    dfs(H, W, D, A, Q, LR, ans)

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


if __name__ == "__main__":
    main()

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

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

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

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

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

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

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

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  

H,W,D = MI()
A = [LI() for i in range(H)]
d = {}
for i in range(H):
    for j in range(W):
        d[A[i][j]] = (i,j)

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

Q = I()
for i in range(Q):
    L,R = MI()
    print(B[R]-B[L])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



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

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

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

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())
g = [[] for _ in range(w)]
for _ in range(h):
    tmp_list = list(map(int, input().split()))
    for i in range(w):
        g[i].append(tmp_list[i])
q = int(input())
qs = [list(map(int, input().split())) for _ in range(q)]
loc = [0]*(h*w+1)
for i in range(h):
    for j in range(w):
        loc[g[j][i]] = (i,j)
roots = [0]*(h*w+1)
for i in range(1,d+1):
    j = i + d
    while j < h*w+1:
        cost = abs(loc[j][0]-loc[j-d][0]) + abs(loc[j][1]-loc[j-d][1])
        roots[j] = cost + roots[j-d]
        j += d
for i in qs:
    l, r = i[0], i[1]
    print(roots[r] - roots[l])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7


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

dic = defaultdict(tuple)

for y in range(H):
	for x in range(W):
		dic[A[y][x]] = (y+1, x+1)

power = [[] for _ in range(D)]
for i in range(1, H*W+1):
	if i <= D:
		power[i%D].append(0)
	else:
		idx = i%D
		tmp = abs(dic[i][0]-dic[i-D][0]) + abs(dic[i][1]-dic[i-D][1])
		power[i%D].append(tmp)


power_acc = []
for x in power:
	power_acc.append(list(accumulate(x)))
power_acc[0].insert(0, 0)


Q = INT()
for _ in range(Q):
	L, R = MAP()
	print(power_acc[R%D][R//D] - power_acc[L%D][L//D])

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7


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

dic = defaultdict(tuple)

for y in range(H):
	for x in range(W):
		dic[A[y][x]] = (y+1, x+1)

power = [[] for _ in range(D)]
for i in range(1, H*W+1):
	if i <= D:
		power[i%D].append(0)
	else:
		idx = i%D
		tmp = abs(dic[i][0]-dic[i-D][0]) + abs(dic[i][1]-dic[i-D][1])
		power[i%D].append(tmp)


power_acc = []
for x in power:
	power_acc.append(list(accumulate(x)))


Q = INT()
for _ in range(Q):
	L, R = MAP()
	if L%D:
		print(power_acc[R%D][R//D] - power_acc[L%D][L//D])
	else:
		print(power_acc[R%D][R//D-1] - power_acc[L%D][L//D-1])

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr



def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


inf = 10 ** 18
mod = 10 ** 9 + 7

h,w,d = lr()
a = [lr() for i in range(h)]
dic = [[0,0] for i in range(h*w)]
dic1 = [[0] for i in range(d)]
for i in range(h):
    for j in range(w):
        dic[a[i][j]-1] = [i,j]
for j in range(d):
    pre = dic[j]
    for k in range(j,h*w,d):
        cost = abs(pre[0] - dic[k][0])+abs(pre[1] - dic[k][1])
        dic1[j].append(dic1[j][-1]+cost)
        pre = dic[k]
q = ir()
for t in range(q):
    l,r = lr()
    l-=1
    r-=1
    next = (r-l)//d
    start = l%d
    left = l//d+1
    print(dic1[start][left+next]-dic1[start][left])

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

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

def dist(i, j):
    dh = abs(i//w - j//w)
    dw = abs(i%w - j%w)
    return dh + dw

idx_list = [0] * n
for i in range(n):
    idx_list[a[i]] = i

dist_list = [0]*n
for i in range(n):
    if i < d:
        dist_list[i] = 0
    else:
        dist_list[i] = dist_list[i-d] + dist(idx_list[i-d], idx_list[i])

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

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

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


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

Solution (Python):
import sys
read = sys.stdin.buffer.read
inp = iter(map(int, read().split()))

H, W, D = next(inp), next(inp), next(inp)
addr = [None] * (H*W+1)
for i in range(H):
    for j in range(W):
        v = next(inp)
        addr[v] = (i, j)

cost = []
for m in range(D):
    arr = [0]
    for x in range((H*W-m)//D):
        if m + x * D == 0:
            arr.append(0)
            continue
        r, c = addr[m + x * D]
        nr, nc = addr[m + (x+1) *D]
        arr.append(arr[-1] + abs(nr - r) + abs(nc - c))
    cost.append(arr)

Q = next(inp)
for _ in range(Q):
    s, t = next(inp), next(inp)
    m = s % D
    ans = cost[m][t//D] - cost[m][s//D]
    print(ans)

Solution (Python):
h, w, d = map(int, input().split())
a = []
for _ in range(h):
    a.append(list(map(int, input().split())))
q = int(input())
querys = []
for _ in range(q):
    l, r = map(int, input().split())
    querys.append((l-1, r-1))
coor = [None]*(h*w)
for i in range(h):
    for j in range(w):
        coor[a[i][j]-1] = (i, j)
accu = [0]*(h*w)
for i in range(d, h*w):
    px, py = coor[i-d]
    x, y = coor[i]
    accu[i] = accu[i-d] + abs(x-px) + abs(y-py)
for l, r in querys:
    print(accu[r]-accu[l])

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w,d=LI()
  l=[LI() for _ in range(h)]

  q=I()
  ql=[LI() for _ in range(q)]

  dic={}
  for i in range(h):
    for j in range(w):
      x=l[i][j]
      dic[x]=(i+1,j+1)

  n=h*w
  to_last_distance=[0]*n
  for i in range(1,n+1)[::-1]:
    if i+d<=n:
      i_y,i_x=dic[i]
      ipd_y,ipd_x=dic[i+d]
      to_last_distance[i-1]=to_last_distance[i+d-1]
      to_last_distance[i-1]+=(abs(i_y-ipd_y)+abs(i_x-ipd_x))

  

  ans=[]
  for st,ed in ql:
    ans.append(to_last_distance[st-1]-to_last_distance[ed-1])

  for x in ans:
    print(x)

main()

Solution (Python):
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    H, W, D = NMI()
    grid = [NLI() for i in range(H)]
    Q = NI()
    querys = [NLI() for i in range(Q)]

    point = [[-1,-1] for _ in range(H*W + 1)]
    for h in range(H):
        for w in range(W):
            a = grid[h][w]
            point[a] = [h, w]

    cost_S = [0] * (H*W + 1)
    for c in range(H*W + 1):
        if c <= D:
            continue

        cost_S[c] = cost_S[c-D] + abs(point[c][0] - point[c-D][0]) + abs(point[c][1] - point[c-D][1])

    for query in querys:
        l, r = query
        print(cost_S[r] - cost_S[l])


if __name__ == "__main__":
    main()

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

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w,d = list(map(int, input().split()))
a = [None]*h
n = h*w
dd = [None]*(n)
for i in range(h):
    a[i] = list(map(int, input().split()))
    for j,num in enumerate(a[i]):
        dd[num-1] = (i,j)
vals = [[] for _ in range(d)]
for i in range(d):
    l = []
    prev = i
    s = 0
    for j in range(i, n, d):
        v = abs(dd[j][0]-dd[prev][0]) + abs(dd[j][1]-dd[prev][1])
        s += v
        l.append(s)
        prev = j
    vals[i] = l
q = int(input())
ans = [None]*q
for i in range(q):
    ll,rr = map(lambda x: int(x)-1, input().split())
    ans[i] = vals[rr%d][rr//d] - vals[ll%d][ll//d]
write("\n".join(map(str, ans)))

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")

INF = float("inf")


H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
table = [[-1,-1] for _ in range(H*W+1)]
for i in range(H):
    for j in range(W):
        a = A[i][j]
        if a > D:
            table[a-D][0] = i
            table[a-D][1] = j
magic = [0]*(H*W+1)
for i in range(H):
    for j in range(W):
        a = A[i][j]
        if a <= H*W-D:
            magic[a] = abs(i-table[a][0])+abs(j-table[a][1])
for i in range(D+1,H*W+1):
    magic[i] += magic[i-D]
Q = int(input())
ans = 0
for i in range(Q):
    L,R = map(int,input().split())
    if L == R:
        print(0)
    else:
        if L <= D:
            print(magic[R-D])
        else:
            print(magic[R-D]-magic[L-D])

Solution (Python):
H, W, D = map(int, input().split())
d, px, py = [0]*(H*W+1), [0]*(H*W+1), [0]*(H*W+1)

for i in range(H):
    a = list(map(int, input().split()))
    for j in range(W):
        px[a[j]] = i
        py[a[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])



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

Solution (Python):
import sys
from itertools import combinations
def input(): return sys.stdin.readline().strip()


def main():
    H, W, D = map(int, input().split())
    place = {}
    for i in range(H):
        A = list(map(int, input().split()))
        for j in range(W):
            place[A[j] - 1] = (i, j)
    magic = [0] * (H * W)
    for n in range(D):
        val = n
        x, y = place[val]
        while val + D < H * W:
            nx, ny = place[val + D]
            magic[val + D] = abs(nx - x) + abs(ny - y) + magic[val]
            val += D
            x, y = nx, ny
    

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


if __name__ == "__main__":
    main()

Solution (Python):
H, W, D = map(int, input().split())
dic = {}
memo = [0]*(H*W+1)

for i in range(H):
  s = input().split()
  for j in range(W):
    dic[int(s[j])] = (i,j)
    
for i in range(1,H*W+1):
  if i - D >= 1:
    memo[i] = memo[i-D] + abs(dic[i][0]-dic[i-D][0]) + abs(dic[i][1]-dic[i-D][1])
    
Q = int(input())
for _ in range(Q):
  l, r = map(int, input().split())
  print(memo[r]-memo[l])

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

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

for i in range(H):
    for j in range(W):
        lst[A[i][j]-1] = [j, i]
tr = [[0] for _ in range(D)]
for i in range(D):
    for j in range(i+D, W*H, D):
        dlt = abs(lst[j][0] - lst[j-D][0]) + abs(lst[j][1] - lst[j-D][1])
        tr[i].append(tr[i][-1] + dlt)

Q = int(input())

for i in range(Q):
    l, r = map(int, input().split())
    idx = (l - 1) % D
    if (l-1)//D == 0: st = 0
    else: st = (l - 1) // D
    ed = (r - 1) // D
    print(tr[idx][ed] - tr[idx][st])

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

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

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

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

print(*result, sep='\n')

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

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

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

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

Solution (Python):
h,w,d = map(int,input().split())
a = [0]*h
for i in range(h):
    a[i] = list(map(int,input().split()))
num = [[] for i in range(w*h+1)]
for i in range(h):
    for j in range(w):
        num[a[i][j]].append([i,j])
s = [0]*(h*w+1)
for i in range(1,h*w-d+1):
    s[d+i] = s[i] + abs(num[d+i][0][0]-num[i][0][0]) + abs(num[d+i][0][1]-num[i][0][1])
q = int(input())
for i in range(q):
    L,R = map(int,input().split())
    print(s[R]-s[L])

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    H, W, D = in_nn()
    A = [list(map(int, readline().split())) for _ in range(H)]
    Q = in_n()
    LR = [list(map(int, readline().split())) for _ in range(Q)]

    grid = [tuple()] * (H * W + 1)
    for y in range(H):
        for x in range(W):
            num = A[y][x]
            grid[num] = (x + 1, y + 1)

    move = [[] for _ in range(D)]
    for i in range(D):
        if i == 0:
            s = D
        else:
            s = i
        while s <= H * W:
            move[i].append(grid[s])
            s += D

    d = [[] for _ in range(D)]
    for i in range(D):
        d[i].append(0)
        for j in range(len(move[i]) - 1):
            x, y = move[i][j]
            nx, ny = move[i][j + 1]
            d[i].append(abs(nx - x) + abs(ny - y))

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

    

    ans = [0] * Q
    for i in range(Q):
        l, r = LR[i]
        q1, rr = divmod(l, D)
        q2, _ = divmod(r, D)
        if rr == 0:
            ans[i] = d[rr][q2 - 1] - d[rr][q1 - 1]
        else:
            ans[i] = d[rr][q2] - d[rr][q1]

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


if __name__ == '__main__':
    main()

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

nums={}
for i in range(h):
    for j in range(w):
        nums[a[i][j]]=(i,j)

acc=[0]*(h*w)
for i in range(h*w):
    if i>=d:
        _to=nums[i+1]
        _from=nums[i+1-d]
        acc[i]+=acc[i-d]+abs(_from[0]-_to[0])+abs(_from[1]-_to[1])

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

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

base = []
for h in range(H):
    num = list(map(int, input().split()))
    for w in range(W):
        base.append((num[w], h+1, w+1))

base.sort(key=lambda tup:tup[0])
dist = [0]*(W*H+D+1)
for i in range(W*H-D):
    wei1, h1, w1 = base[i]
    wei2, h2, w2 = base[i+D]
    dist[i+D] = dist[i] + abs(h1-h2) + abs(w1-w2)

Q = int(input())
for _ in range(Q):
    p0, p1 = map(int, input().split())
    print(abs(dist[p1-1]-dist[p0-1]))

Solution (Python):
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

l = []

for h in range(H):
    for w in range(W):
        l.append((A[h][w], w, h))

l.sort()

S = [0] * (H * W + D + 10)

for i, x, y in l:
    if i + D <= H * W:
        _, xx, yy = l[i + D - 1]
        S[i + D] = abs(xx - x) + abs(yy - y) + S[i]

Q = int(input())

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

Solution (Python):


def calc(x):
    if x<D+1:
        mv[x]=0
        return 0
    else:
        p = d[x][0]
        q = d[x][1]
        r = d[x-D][0]
        s = d[x-D][1]
        tmp = abs(p-r)+abs(q-s)
        ret= tmp+calc(x-D)
        mv[x]=ret
        return ret

import sys 
sys.setrecursionlimit(10**5)
H,W,D= map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
Q=int(input())

d=dict()
z=0
for a in A:
    for b in a:
        p = z//W
        q = z%W
        d[b]=(p,q)
        z+=1
        
mv=[0]*(H*W+1)
for i in range(D):
    calc(H*W-i)
    


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

Solution (Python):
H,W,D = map(int,input().split())
px = [0]*90001
py = [0]*90001
for i in range(H):
    A = list(map(int,input().split()))
    for j in range(len(A)):
        px[A[j]] = i+1
        py[A[j]] = j+1
d = [0]*90001
Q = int(input())
for i in range(D+1,H*W+1,1):
    d[i] = d[i-D] + abs(px[i]-px[i-D]) + abs(py[i]-py[i-D])
for _ in range(Q):
    l,r = map(int,input().split())
    print(d[r]-d[l])

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    h,w,d = map(int,ipt().split())
    pl = [(-1,-1)]*(h*w+1)
    for i in range(h):
        a = [int(i) for i in ipt().split()]
        for j,aj in enumerate(a):
            pl[aj] = (i,j)
    ssl = [0]*(h*w+1)
    for i in range(d+1,h*w+1):
        ssl[i] = ssl[i-d]+abs(pl[i-d][0]-pl[i][0])+abs(pl[i-d][1]-pl[i][1])
    q = int(ipt())
    for _ in range(q):
        l,r = map(int,ipt().split())
        print(ssl[r]-ssl[l])

    return

if __name__ == '__main__':
    main()