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):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






"""

N = 10
num = [i for i in range(1, N + 1)]
D = 2
lista = [0] * N
for i in range(D):
    for j in range(i, N, D):
        if j == i:
            lista[j] = num[j]
        else:
            lista[j] = num[j] + lista[j - D]

print(lista)


print(lista[8] - lista[0])
"""


H, W, D = getNM()
maze = []
for i in range(H):
    a = getList()
    maze.append(a)
Q = getN()


piece = []
for i in range(Q):
    l, r = getNM()
    piece.append([l, r])

place_list = [[-1, -1] for i in range(H * W)]

for y in range(H):
    for x in range(W):
        place_list[maze[y][x] - 1] = [x, y]


x_plus = [0] * (H * W)
y_plus = [0] * (H * W)
for i in range(D):
    for j in range(i, H * W, D):
        if j == i:
            opt_x = 0
            opt_y = 0
        else:
            opt_x = abs(place_list[j][0] - place_list[j - D][0])
            opt_y = abs(place_list[j][1] - place_list[j - D][1])
            x_plus[j] = opt_x + x_plus[j - D]
            y_plus[j] = opt_y + y_plus[j - D]

def past_exam(piece_query):
    start = piece_query[0]
    goal = piece_query[1]

    x_point = x_plus[goal - 1] - x_plus[start - 1]
    y_point = y_plus[goal - 1] - y_plus[start - 1]
    return x_point + y_point

for i in range(Q):
    print(past_exam(piece[i]))

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7







H, W, D = getNM()
maze = []
for i in range(H):
    a = getList()
    maze.append(a)
Q = getN()


piece = []
for i in range(Q):
    l, r = getNM()
    piece.append([l, r])

place_list = [[-1, -1] for i in range(H * W)]

for y in range(H):
    for x in range(W):
        place_list[maze[y][x] - 1] = [x, y]


x_plus = []
y_plus = []
for i in range(D):
    list_x = [0]
    list_y = [0]
    for j in range(i, H * W, D):
        if j == i:
            opt_x = 0
            opt_y = 0
        else:
            opt_x = abs(place_list[j][0] - place_list[j - D][0])
            opt_y = abs(place_list[j][1] - place_list[j - D][1])
        list_x.append(list_x[-1] + opt_x)
        list_y.append(list_y[-1] + opt_y)
    list_x.pop(0)
    list_y.pop(0)
    x_plus.append(list_x)
    y_plus.append(list_y)

def past_exam(piece_query):
    start = piece_query[0]
    goal = piece_query[1]

    mul = (start - 1) % D
    if D == 1:
        x_point = x_plus[0][goal - 1] - x_plus[0][start - 1]
        
        y_point = y_plus[0][goal - 1] - y_plus[0][start - 1]
    else:
        x_point = x_plus[mul][(goal - mul) // D] - x_plus[mul][(start - mul) // D]
        y_point = y_plus[mul][(goal - mul) // D] - y_plus[mul][(start - mul) // D]
    return x_point + y_point

for i in range(Q):
    print(past_exam(piece[i]))

Solution (Python):
h,w,d=map(int, input().split())
a=[list(map(int,list(input().split()))) for _ in range(h)]
p=[0]*(h*w+1)
for i in range(h):
    for j in range(w):
        p[a[i][j]]=(i,j)

c=[0]*(h*w+1) 
for i in range(d+1,h*w+1):
    c[i]=c[i-d]+abs(p[i][0]-p[i-d][0])+abs(p[i][1]-p[i-d][1])
q=int(input())
ans=0
for i in range(q):
    l,r=map(int, input().split())
    print(c[r]-c[l])

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

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

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

for i in range(d+1,h*w+1):
    if i-d not in dic:
        continue
    li[i] = li[i-d] + abs(dic[i][0]-dic[i-d][0]) + abs(dic[i][1]-dic[i-d][1])

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

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

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

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

for i in range(d+1,h*w+1):
    if i-d not in dic:
        continue
    li[i] = li[i-d] + abs(dic[i][0]-dic[i-d][0]) + abs(dic[i][1]-dic[i-d][1])

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

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

idx=[0]*(H*W)
for h in range(H):
    for w in range(W):
        num=A[h][w]
        idx[num-1]=[h+1,w+1]
acum=[0]*(H*W+1)
for i in range(1,H*W+1):
    if i-D<=0:
        acum[i]=sum(idx[i-1])
    else:
        prex,prey=idx[i-1-D]
        nexx,nexy=idx[i-1]
        acum[i]=acum[i-D]+abs(nexx-prex)+abs(nexy-prey)



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

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

    H, W, D = map(int, input().split())
    B = [0] * (H * W)

    C = [None] * (H * W)
    for r in range(H):
        for c, cell in enumerate(int(x) - 1 for x in input().split()):
            C[cell] = r, c

    for x in range(D, H * W):
        L, R = x - D, x
        lr, lc = C[L]
        rr, rc = C[R]
        B[R] = B[L] + abs(rr - lr) + abs(rc - lc)

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

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


if __name__ == '__main__':
    main()

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

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

dic = {}

for i in range(H):
  temp = list(map(int,input().split()))
  for j in range(W):
    now = temp[j]
    dic[now] = (i,j)

L = [[0] for _ in range(D)]
for i in range(D): 
  if i == 0:
    now = D
  else:
    now = i
  while now+D <= MAX:
    tsugi = now+D
    np = dic[now] 
    tp = dic[tsugi]
    dis = abs(np[0]-tp[0])+abs(np[1]-tp[1])
    L[i].append(L[i][-1]+dis)
    now = tsugi

Q = int(input())
for i in range(Q):
  left,right = map(int,input().split())
  MOD = left%D
  
  start = (left-1)//D
  end = (right-1)//D
  ans = L[MOD][end]-L[MOD][start]
  print(ans)

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

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

    B = [0] * (H * W)

    C = [None] * (H * W)
    for r, row in enumerate(A):
        for c, cell in enumerate(row):
            C[cell - 1] = r, c

    for x in range(D, H * W):
        L, R = x - D, x
        lr, lc = C[L]
        rr, rc = C[R]
        B[R] = B[L] + abs(rr - lr) + abs(rc - lc)

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

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


if __name__ == '__main__':
    main()

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

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

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

    C = [None] * (H * W)
    for r, row in enumerate(A):
        for c, cell in enumerate(row):
            C[cell - 1] = r, c

    for x in range(H * W):
        r = x % D
        if B[r]:
            cr, cc = C[x]
            pr, pc = C[x - D]
            cost = abs(cr - pr) + abs(cc - pc)
            B[r].append(B[r][-1] + cost)

        else:
            B[r].append(0)

    ans = []
    Q = int(input())
    for _ in range(Q):
        L, R = (int(x) - 1 for x in input().split())
        r = R % D
        ql, qr = L // D, R // D

        ans.append(B[r][qr] - B[r][ql])

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    H, W, d = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    q = int(input())

    XY = [[] for _ in range(H * W)]
    for h in range(H):
        for w in range(W):
            XY[A[h][w] - 1] = [h, w]
    R = [0] * (H * W + 1)
    for i in range(1, H * W + 1):
        if i - d > 0:
            x1, y1 = XY[i - 1]
            x2, y2 = XY[i - 1 - d]
            cost = abs(x1 - x2) + abs(y1 - y2)
            R[i] = R[i - d] + cost

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


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

from collections import defaultdict

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

dic = defaultdict(list)

for h in range(H):
    for w in range(W):
        dic[A[h][w]] = [h, w]

def calc(l, r):
    return abs(dic[l][0] - dic[r][0]) + abs(dic[l][1] - dic[r][1])

lst = [0] * (H * W + 1)
for d in range(1, D + 1):
    tmp = d
    while tmp + D <= (H * W):
        lst[tmp + D] = lst[tmp] + calc(tmp, tmp + D)
        tmp += D


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

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

h,w,d = inpl()
n = h*w
di = dict()
for i in range(h):
    x = inpl()
    for j in range(w):
        di[x[j]-1] = (i,j)
a = []
for i in range(d):
    tmp = [0]
    for j in range(i,n,d):
        if j == i:
            px,py = di[j]
            continue
        nx,ny = di[j]
        tmp.append(abs(nx-px)+abs(ny-py))
        px,py = nx,ny
    a.append(list(itertools.accumulate(tmp)))

q = inp()
for _ in range(q):
    l,r = inpl()
    l,r = l-1, r-1
    now = l%d
    print(a[now][(r-now)//d] - a[now][(l-now)//d])

Solution (Python):
from sys import stdin
def main():
    
    readline=stdin.readline
    h,w,d=map(int,readline().split())
    a=[list(map(int,readline().split())) for _ in range(h)]
    q=int(readline())
    l=[0]*q
    r=[0]*q
    for i in range(q):
        l[i],r[i]=map(int,readline().split())

    
    co=dict()
    for i in range(h):
        for j in range(w):
            co[a[i][j]]=(i,j)

    
    s=[0]*(h*w+1)
    for i in range(1,d+1):
        j=i+d
        while j<=h*w:
            distance=abs(co[i][0]-co[j][0])+abs(co[i][1]-co[j][1])
            s[j]+=s[i]+distance
            i+=d
            j+=d

    
    for i in range(q):
        print(s[r[i]]-s[l[i]])

if __name__=="__main__":
    main()

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

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

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

acc = [[0] for _ in range(D)]

for i in range(D):
    now = i
    
    while now+D<H*W:
        cost = abs(x[now]-x[now+D])+abs(y[now]-y[now+D])
        acc[i].append(acc[i][-1]+cost)
        now += D

Q = int(input())

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

Solution (Python):
from functools import lru_cache
import sys
sys.setrecursionlimit(10**7)

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

A = [list(map(int, input().split())) for _ in range(H)]
aToHW = {}
for h, row in enumerate(A):
    for w, a in enumerate(row):
        aToHW[a] = (h, w)

Q = int(input())

@lru_cache(maxsize=None)
def search(now):
    if not now + D in aToHW:
        return 0

    l, r = aToHW[now], aToHW[now + D]
    return abs(l[0] - r[0]) + abs(l[1] - r[1]) + search(now + D)

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

    ans.append(search(l) - search(r))

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

Solution (Python):
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

h,w,d=mp()
l=[[]for i in range(h*w+1)]
for i in range(h):
    a=lmp()
    for k in range(w):
        l[a[k]]=[i,k]
ans=[0]*(h*w+1)
for i in range(1,d+1):
    for k in range((h*w-i)//d):
        ans[i+(k+1)*d]=ans[i+k*d]+abs(l[i+k*d][0]-l[i+(k+1)*d][0])+abs(l[i+k*d][1]-l[i+(k+1)*d][1])
q=int(input())
for i in range(q):
     l,r=mp()
     print(ans[r]-ans[l])

Solution (Python):
import math
h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
lis = [[0,0] for i in range(h * w)]
num = [[0] * math.ceil((h * w) // d + 1) for i in range(d)]
for i in range(h):
    for j in range(w):
        lis[a[i][j]-1] = [i,j]
for i in range(h * w-d):
    num[i%d][i//d+1] = num[i%d][i//d]+abs(lis[i][0]-lis[i+d][0])+abs(lis[i][1]-lis[i+d][1])
q = int(input())
for _ in range(q):
    now,goal = map(int,input().split())
    if now % d == 0:
        print(num[now%d-1][(goal-now%d)//d-1]-num[now%d-1][(now-now%d)//d-1])
    else:
        print(num[now%d-1][(goal-now%d)//d]-num[now%d-1][(now-now%d)//d])

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 8)

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    H, W, D = ZZ()
    A = [ZZ() for _ in range(H)]
    Q = Z()
    query = [ZZ() for _ in range(Q)]

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

    def calc(now, c):
        cost[now] = c
        if now+D > H*W: return
        x, y = pos[now]
        nx, ny = pos[now+D]
        nc = abs(nx-x) + abs(ny-y) + c
        calc(now + D, nc)

    for n in range(1, D+1): calc(n, 0)

    for l, r in query: print(cost[r] - cost[l])

    return

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

h,w,d=mp()
l=[[]for i in range(h*w+1)]
for i in range(h):
    a=lmp()
    for k in range(w):
        l[a[k]]=[i,k]
ans=[0]*(h*w+1)
for i in range(1,d+1):
    for k in range((h*w-i)//d):
        ans[i+(k+1)*d]=ans[i+k*d]+abs(l[i+k*d][0]-l[i+(k+1)*d][0])+abs(l[i+k*d][1]-l[i+(k+1)*d][1])
q=int(input())
for i in range(q):
     l,r=mp()
     print(ans[r]-ans[l])

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

def calcdist(i,j):
  return abs(place[i][0]-place[j][0])+abs(place[i][1]-place[j][1])

dp=[[0] for i in range(d+1)]
for i in range(1,d+1):
  for j in range(i+d,h*w+1,d):
    dp[i].append(dp[i][-1]+calcdist(j-d,j))
    
q=int(input())
for _ in range(q):
  l,r=map(int,input().split())
  i=l%d
  if i==0:
    i=d
  l=(l-1)//d
  r=(r-1)//d
  print(dp[i][r]-dp[i][l])

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

def calcdist(i,j):
  return abs(place[i][0]-place[j][0])+abs(place[i][1]-place[j][1])

dp=[[0] for i in range(d+1)]
for i in range(1,d+1):
  for j in range(i+d,h*w+1,d):
    dp[i].append(dp[i][-1]+calcdist(j-d,j))
    
q=int(input())
for _ in range(q):
  l,r=map(int,input().split())
  i=l%d
  if i==0:
    i=d
  l=(l-1)//d
  r=(r-1)//d
  print(dp[i][r]-dp[i][l])

Solution (Python):


import sys
























from itertools import accumulate             





def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    def make_chain(res, seq):
        num = res
        prev = number_to_point[num]
        num += d
        while num < h * w:
            current = number_to_point[num]
            dist = abs(current[0] - prev[0]) + abs(current[1] - prev[1])
            seq.append(dist)
            num += d
            prev = current
            

    
    h, w, d = mi()
    grid = [lmi_0() for _ in range(h)]    
    q = ii()
    query = [lmi_0() for _ in range(q)]

    number_to_point = dict()
    for i in range(h):
        for j in range(w):
            number_to_point[grid[i][j]] = (i, j)

    chain = [[0] for _ in range(d)]    
    for i in range(d):
        make_chain(i, chain[i])
    
    
    
    accum_chain = [list(accumulate(elm)) for elm in chain]

    for l, r in query:
        assert (l % d == r % d)
        res = l % d
        a = l // d
        b = r // d
        print(accum_chain[res][b] - accum_chain[res][a])




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())
query = [list(map(int, input().split())) for _ in range(q)]

MAXH = 300
MAXW = 300

pos = [[] for _ in range(MAXH*MAXW+10)]
for i in range(h):
    for j in range(w):
        s = a[i][j]
        pos[s] = [i, j]

score = [0 for _ in range(MAXH*MAXW+10)]
for i in range(1, d+1):
    n = i
    while n+d <= h*w:
        x, y = pos[n]
        nx, ny = pos[n+d]
        score[n+d] += score[n]+abs(nx-x)+abs(ny-y)
        n += d

for loop in range(q):
    l, r = query[loop]
    print(score[r]-score[l])

Solution (Python):
def main():
  H, W, D = map(int, input().split())
  num = [[] for _  in range(H*W)]
  for i in range(H):
    temp = list(map(int, input().split()))
    for j in range(len(temp)):
      num[temp[j]-1] = [i, j]
  
  num_sum = [0]*(H*W)
  for i in range(D, H*W):
    num_sum[i] = num_sum[i-D] + (abs(num[i][0]-num[i-D][0])+ abs(num[i][1]-num[i-D][1]))
  Q = int(input())
  ans = []
  for i in range(Q):
    L, R = map(int, input().split())
    ans.append(num_sum[R-1]-num_sum[L-1])
  print(*ans, sep='\n')
if __name__ == "__main__":
  main()

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

a_to_ij = {}
for i, aa in enumerate(A):
  for j, a in enumerate(aa):
    a_to_ij[a] = (i, j)

cost = {}
def calc_cost(s):
  global cost
  t = s
  pre_i, pre_j = a_to_ij[s]
  c = cost[s] = 0
  while t + D <= M:
    t += D
    i, j = a_to_ij[t]
    c += abs(i-pre_i) + abs(j-pre_j)
    cost[t] = c
    pre_i, pre_j = i, j

for n in range(1, D+1):
  calc_cost(n)

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

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

Solution (Python):
def main():
  H, W, D = map(int, input().split())
  num = [[] for _  in range(H*W)]
  for i in range(H):
    temp = list(map(int, input().split()))
    for j in range(len(temp)):
      num[temp[j]-1] = [i, j]
  
  num_sum = [0]*(H*W)
  for i in range(D, H*W):
    num_sum[i] = num_sum[i-D] + (abs(num[i][0]-num[i-D][0])+ abs(num[i][1]-num[i-D][1]))
  Q = int(input())
  for i in range(Q):
    L, R = map(int, input().split())
    print(num_sum[R-1]-num_sum[L-1])
if __name__ == "__main__":
  main()

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

a_to_ij = {}
for i, aa in enumerate(A):
  for j, a in enumerate(aa):
    a_to_ij[a] = (i, j)

cost = {}
def calc_cost(s):
  global cost
  t = s
  pre_i, pre_j = a_to_ij[s]
  c = cost[(s, s)] = 0
  while t + D <= M:
    t += D
    i, j = a_to_ij[t]
    c += abs(i-pre_i) + abs(j-pre_j)
    cost[(s, t)] = c
    pre_i, pre_j = i, j

for n in range(1, D+1):
  calc_cost(n)

ans = []
Q = int(input())
for i in range(Q):
  L, R = map(int, input().split())
  s = L % D
  if s == 0:
    s = D
  ans.append(cost[(s, R)] - cost[(s, L)])

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

Solution (Python):
def main():
  H, W, D = map(int, input().split())
  num = [[] for _  in range(H*W)]
  for i in range(H):
    temp = list(map(int, input().split()))
    for j in range(len(temp)):
      num[temp[j]-1] = [i, j]
  
  num_sum = [0]*(H*W)
  for i in range(D, H*W):
    num_sum[i] = num_sum[i-D] + (abs(num[i][0]-num[i-D][0])+ abs(num[i][1]-num[i-D][1]))
  Q = int(input())
  for i in range(Q):
    L, R = map(int, input().split())
    print(num_sum[R-1]-num_sum[L-1])
if __name__ == "__main__":
  main()

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

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

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

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

Solution (Python):
h,w,z = map(int,input().split())
a_mat = []
for i in range(h):
  a_list = list(map(int,input().split()))
  a_mat.append(a_list)
pos_dic  = {}
for i in range(h):
  for j in range(w):
    pos_dic[a_mat[i][j] - 1] = [i,j]
    
d = [0 for i in range(h*w)]
for a in range(z,h*w):
  d[a] = d[a-z] + abs(pos_dic[a][0] - pos_dic[a-z][0]) +abs(pos_dic[a][1] - pos_dic[a-z][1])
  
q = int(input())
for _ in range(q):
  l,r = map(int,input().split())
  print(d[r-1] - d[l-1])

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

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

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

s = [[] for _ in range(D+1)]
for i in range(1,D+1):
    cost = 0
    s[i].append(0)
    for j in range(i,H*W-D+1,D):
        cost += abs(d[j][0] - d[j+D][0]) + abs(d[j][1] - d[j+D][1])
        s[i].append(cost)

Q = int(input())
for i in range(Q):
    L,R = map(int,(input().split()))
    r = L%D
    if r == 0:
        r = D
    ans = s[r][(R-r)//D]-s[r][(L-r)//D]
    print(ans)

Solution (Python):
def main():
    H, W, D = list(map(int, input().split(' ')))
    cell_list = list()
    for h in range(H):
        a_list = list(map(int, input().split(' ')))
        cell_list.extend([(a - 1, h, w) for w, a in enumerate(a_list)])
    cell_list.sort(key=lambda c: c[0])  
    
    cumsum = dict()
    for d in range(D):
        cumsum[d] = [0]
    for x in range(D, H * W):
        d = x % D
        bef_c, c = cell_list[x - D], cell_list[x]
        m = cumsum[d][-1] + abs(c[1] - bef_c[1]) + abs(c[2] - bef_c[2])
        cumsum[d].append(m)
    
    Q = int(input())
    queries = [list(map(lambda x: int(x) - 1, input().split(' '))) for _ in range(Q)]
    for L, R in queries:
        d = L % D
        print(cumsum[d][R // D] - cumsum[d][L // D])


if __name__ == '__main__':
    main()

Solution (Python):
H, W, D = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]
target = [[0,0] for _ in range(H*W+1)]
ruiseki = [[i+1] for i in range(D)]
ans = 0
for i in range(H):
    for j in range(W):
        target[grid[i][j]][0] = i+1
        target[grid[i][j]][1] = j+1
for i in range(D):
    tmp = ruiseki[i][0]
    ruiseki[i][0] = 0
    cnt = 0
    while tmp+D <= H*W:
        dist = abs(target[tmp][0]-target[tmp+D][0])+abs(target[tmp][1]-target[tmp+D][1])
        ruiseki[i].append(ruiseki[i][cnt]+dist)
        cnt += 1
        tmp += D
for i in range(Q):
    current = LR[i][0]
    tmp = D if current%D == 0 else current%D
    tmp -= 1
    print(ruiseki[tmp][((current-1)//D)+((LR[i][1]-current)//D)]-ruiseki[tmp][((current-1)//D)])

Solution (Python):
H, W, D = map(int, input().split())
A = [list(map(lambda s: int(s) - 1, input().split())) for i in range(H)]
Q = int(input())
queries = [tuple(map(lambda s: int(s) - 1, input().split())) for i in range(Q)]

T = {}
for i in range(H):
    for j in range(W):
        T[A[i][j]] = (i, j)
accum = [[0] for i in range(D)]
for i in range(D):
    for j in range(i + D, H * W, D):
        p = T[j - D]
        n = T[j]
        accum[i].append(accum[i][-1] + abs(p[0] - n[0]) + abs(p[1] - n[1]))

for query in queries:
    r = query[0] % D
    print(accum[r][query[1] // D] - accum[r][query[0] // D])

Solution (Python):
h,w,d=map(int,input().split())
a=[]
box=[[] for i in range(h*w+1)]
wi=0
for i in range(h):
    ai=list(map(int,input().split()))
    for j in range(w):
        box[ai[j]]=[i,j]

p=[0]
for i in range(1,h*w+1):
    if(i-d>0):
        p.append(p[i-d]+abs(box[i][0]-box[i-d][0])+abs(box[i][1]-box[i-d][1]))
    else:
        p.append(0)

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

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

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

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

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

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

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

for i in range(D):
    nowx,nowy=pos[i]
    idx=i
    rui=0
    pos[i]=rui
    while idx+D<H*W:
        idx+=D
        x,y=pos[idx]
        rui=rui+abs(x-nowx)+ abs(y-nowy)
        pos[idx]=rui
        nowx=x
        nowy=y

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

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

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

for i in range(D):
    nowx,nowy=pos[i]
    idx=i
    rui=0
    pos[i]=rui
    while idx+D<H*W:
        idx+=D
        x,y=pos[idx]
        rui=rui+abs(x-nowx)+ abs(y-nowy)
        pos[idx]=rui
        nowx=x
        nowy=y

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

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read
    H, W, D = (int(i) for i in input().split())
    R = [r for r in read().rstrip().split(b'\n')]
    A = [[int(i) for i in r.split()] for r in R[:H]]

    B = [0]*(H*W+1)
    pos = {A[i][j]: (i+1, j+1) for i in range(H) for j in range(W)}

    for i in range(D+1, H*W+1):
        y, x = pos[i - D]
        ny, nx = pos[i]
        power = abs(nx - x) + abs(ny - y)
        B[i] = B[i - D] + power

    for r in R[H+1:]:
        le, ri = (int(i) for i in r.split())
        print(B[ri] - B[le])


if __name__ == '__main__':
    main()