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.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
h,w,d=map(int,input().split())
inds={}
for i in range(h):
    for D,j in enumerate(input().split()):
        inds[int(j)-1]=(i,D)
nows=[[0]for c in range(d)]

for k in range(d,h*w):
    a,b=inds[k]
    x,y=inds[k-d]
    k%=d
    nows[k].append(nows[k][-1]+abs(a-x)+abs(b-y))
q=input()
for i in inputs():
    l,r=map(int,i.split())
    l-=1;r-=1
    l,b=divmod(l,d)
    r,b=divmod(r,d)
    print(nows[b][r]-nows[b][l])

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

from collections import defaultdict
G = defaultdict(list)
for i in range(h):
    l = list(map(int, input().split()))
    for n, item in enumerate(l):
        G[item] = [n,i]










dp = [0 for i in range(h*w+1)]
for i in range(d): 
    current_place = i+1
    while current_place + d <= h*w:
        x,y = G[current_place]
        next_place = current_place + d
        x1,y1 = G[next_place]
        magic = abs(x-x1) + abs(y-y1)
        dp[next_place] = magic + dp[current_place]
        current_place = next_place

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

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)]
b = [0]*(h*w+1)
for i in range(h):
  for j in range(w):
    b[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(b[i][0]-b[i-d][0])+abs(b[i][1]-b[i-d][1])
for l,r in lr:
  print(c[r]-c[l])

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

x = [0]*(H*W+1)
p = [[] for _ in range(H*W+1)]

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

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

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

Solution (Python):
def main():
    H,W,D = map(int,input().split())
    N = H*W
    A = []
    for i in range(H):
        A.append(list(map(int, input().split())))
    places = [0] * (H * W + 1)
    for i in range(H):
        for j in range(W):
            places[A[i][j]] = (i,j)
    dp = [0] * (N+1)
    for i in range(D+1,N+1):
        y1,x1 = places[i-D]
        y2,x2 = places[i]
        dp[i] = dp[i-D]+abs(x1-x2)+abs(y1-y2)
    

    Q = int(input())
    queries = []
    ans = []
    for i in range(Q):
        l,r = map(int,input().split())
        ans.append(dp[r] - dp[l])
    print('\n'.join(map(str,ans)))
main()

Solution (Python):

import sys


sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush

from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
import math

import bisect






INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())



def run():
    H, W, D = mapline()
    A = [[-1] * (W+1) for _ in range(H+1)]
    for i in range(1, H+1):
        A[i][1:] = mapline()

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

    cache = [-1] * (H*W+1)

    Q = intread()
    for _ in range(Q):
        l, r = mapline()
        if cache[r] == -1:
            mostR = r + (H*W - r) // D * D
            mostL = l % D
            if not mostL:
                mostL = D
            ci, cj = V[mostR]
            tmp = 0
            cache[mostR] = 0
            
            for v in range(mostR - D, mostL-D, -D):
                
                ni, nj = V[v]
                tmp += abs(ni - ci) + abs(nj - cj)
                cache[v] = tmp
                ci, cj = ni, nj
        
        print(cache[l] - cache[r])


if __name__ == "__main__":
    
    run()

Solution (Python):
def main():
    h,w,d = map(int,input().split())
    a = []
    for i in range(h):
        a.append(list(map(int,input().split())))
    M = [[] for i in range(h*w)]
    for i in range(h):
        for j in range(w):
            M[a[i][j]-1] = [i,j]
    dist = [0 for i in range(h*w)]
    for i in range(h*w):
        if i-d>=0:
            dist[i] += dist[i-d] + abs(M[i][0]-M[i-d][0]) + abs(M[i][1]-M[i-d][1])

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

if __name__ == "__main__":
    main()

Solution (Python):

def main():
    H, W, D = map(int, input().split())
    coordinate = [None] * (H*W)
    for i in range(H):
        for j, A in enumerate(list(map(int, input().split()))):
            coordinate[A-1] = (i, j)
    
    cost = [0] * (H*W)
    dist = lambda X, Y: abs(X[0]-Y[0]) + abs(X[1]-Y[1])
    for i in range(D, H*W):
        u,v = divmod(i, D)
        cost[i] = cost[i-D] + dist(coordinate[i], coordinate[i-D])

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

main()

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

for x in range(1,h*w+1):
  if x+d<=w*h:
    ans[x+d]=ans[x]+abs(za[x+d][0]-za[x][0])+abs(za[x+d][1]-za[x][1])
    
q=int(input())
for _ in range(q):
  e,f=map(int,input().split())
  print(ans[f]-ans[e])

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect






sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

H, W, D =na()
A = [na() for _ in range(H)]
Q = ni()
d = {}
for i in range(H):
    for j in range(W):
        d[A[i][j]] = (i, j)

dp = [0 for _ in range(H*W+1)]

for i in range(1, D+1):
    dp[i] = 0

for i in range(D+1, H*W+1):
    ni, nj = d[i]
    pi, pj = d[i - D]
    dp[i] = dp[i - D] + abs(ni - pi) + abs(nj - pj)

for i in range(Q):
    ans = 0
    l, r = na()
    ans = dp[r] - dp[l]
    print(ans)

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

Jump = [[0] for _ in range(D+1)]
for i in range(1, D+1):
    total = 0
    for j in range(i, H*W+1-D, D):
        total += abs(P[j+D][0] - P[j][0]) + abs(P[j+D][1] - P[j][1])
        Jump[i].append(total)
Ans = []
for i in range(Q):
    L, R = map(int, input().split())
    k = L % D
    start = L//D
    end = R//D
    if k == 0:
        k += D
        start -= 1
        end -= 1
    Ans.append(Jump[k][end] - Jump[k][start])

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

Solution (Python):
H, W, D = map(int,input().split())
d = {}
for i in range(1, H+1):
    A = list(map(int,input().split()))
    for j in range(W):
        d[A[j]] = (i, j+1)
acc = [[] for _ in range(D)]
for i in range(1, D+1):
    acc[i-1].append(0)
    for j in range(i, H*W+1-D, D):
        x,y = d[j]
        a,b = d[j+D]
        
        acc[i-1].append(acc[i-1][-1]+abs(a-x)+abs(b-y))
    
Q = int(input())
for _ in range(Q):
    l, r = map(int,input().split())
    print(acc[(l-1)%D][(r-1)//D]-acc[(l-1)%D][(l-1)//D])

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

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

for h_ in range(h):
    for w_ in range(w):
        iti[a[h_][w_]].append(w_+1)
        iti[a[h_][w_]].append(h_+1)


s_d = [[] for _ in range(d+1)]
for i in range(1, d+1): 
    now = i
    s_d[i].append(0) 
    while now + d <= h*w:
        s_d[i].append(s_d[i][-1] + abs(iti[now][0]-iti[now+d][0]) + abs(iti[now][1]-iti[now+d][1]))
        now += d


def query(l, r):
    idx = l % d 
    if idx == 0:
        idx = d
    
    
    l_d = l // d
    r_d = r // d
    if l % d == 0:
        l_d -= 1
        r_d -= 1
    cost = s_d[idx][r_d] - s_d[idx][l_d]
    return cost


q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(query(l, r))

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)]
arys=[[] for i in range(d)]
sumarys=[[0] for i in range(d)]
biarys=[[] for i in range(d)]
for i in range(h):
  for j in range(w):
    x=a[i][j]%d
    arys[x].append((a[i][j],i,j))
for i in range(d):
  arys[i].sort(key=lambda x:x[0])
  tmp=0
  y,pi,pj=arys[i][0]
  biarys[i].append(y)
  for j in range(1,len(arys[i])):
    y,ni,nj=arys[i][j]
    biarys[i].append(y)
    tmp+=abs(pi-ni)+abs(pj-nj)
    sumarys[i].append(tmp)
    pi,pj=ni,nj
from bisect import bisect_left
for l,r in lr:
  x=l%d
  li=bisect_left(biarys[x],l)
  ri=bisect_left(biarys[x],r)
  print(sumarys[x][ri]-sumarys[x][li])

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

dst=[0 for i in range(d)]
for i in range(d,n):
  dst.append(abs(a[i-d][0]-a[i][0])+abs(a[i-d][1]-a[i][1]))

s=[0 for i in range(d)]
for i in range(d,n):
  s.append(s[i-d]+dst[i])

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

Solution (Python):


h, w, d = list(map(int, input().split()))

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


data = [[] for _ in range(d)]

for i in range(1, d+1):
    num = i
    x, y = index[num-1]
    data[i-1].append(0)
    num += d
    while(num <= h*w):
        x_new, y_new = index[num-1]
        
        data[i-1].append(abs(x-x_new)+abs(y-y_new)+data[i-1][-1])
        x, y = x_new, y_new
        num += d


q = int(input())
for i in range(q):
    l, r = list(map(int, input().split()))

    index_data = l % d-1

    r = (r-1)//d
    l = (l-1)//d
    print(data[index_data][r]-data[index_data][l])

Solution (Python):
h,w,d= map(int,input().split())
loc=[[] for _ in range(w*h+1)]
cost=[0]*(w*h+1)
for i in range(h):
    l= list(map(int,input().split()))
    for j in range(w):loc[l[j]]=[i,j]
for t in range(w*h+1,0,-1):
    if t+d < w*h+1:
        ti,tj=loc[t+d]
        fi,fj=loc[t]
        tempcost= abs(fi-ti)+abs(fj-tj)
        cost[t]=cost[t+d]+tempcost
q= int(input())
for i in range(q):
    l,r= map(int,input().split())
    print(cost[l]-cost[r])

Solution (Python):
h, w, d = map(int, input().split())
arr = [0] * (h * w + 1)

a = [list(map(int, input().split())) for _ in range(h)]

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

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

cnt = h * w
result = [[0] for _ in range(d)]
for i in range(d):
    l = i
    score = 0
    while l + d <= cnt:
        if l == 0:
            result[i].append(score)
            l += d
            continue
        (ux, uy) = arr[l]
        (vx, vy) = arr[l + d]
        score += (abs(vx - ux) + abs(vy - uy))
        result[i].append(score)
        l += d


for l, r in lr:
    ans = result[l % d]
    print(ans[r // d] - ans[l // d])

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

h,w,d=nii()

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

b_dict={}
for i in range(1,h*w+1):
  if i-d<=0:
    b_dict[i]=0
  else:
    oy,ox=a_dict[i-d]
    ny,nx=a_dict[i]
    b_dict[i]=b_dict[i-d]+abs(ny-oy)+abs(nx-ox)

q=int(input())
for i in range(q):
  l,r=nii()
  ans=b_dict[r]-b_dict[l]
  print(ans)

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


import heapq
sys.setrecursionlimit(10**6)

INF = 10**18
import bisect
import statistics
mod = 10**9+7


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

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

P = [[]]
for i in range(1,D+1):
    q = [0]
    k = i + D
    while k <= H*W:
        p = abs(dict[k][0] - dict[k-D][0]) + abs(dict[k][1] - dict[k-D][1])
        q.append(q[-1]+p)
        k = k + D
    P.append(q)

Q = int(input())

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

Solution (Python):
h, w, d = map(int, input().split())
arr = [0] * (h * w + 1)

a = [list(map(int, input().split())) for _ in range(h)]

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

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

cnt = h * w
result = [[0] for _ in range(d)]
for i in range(d):
    l = i
    score = 0
    while l + d <= cnt:
        if l == 0:
            result[i].append(score)
            l += d
            continue
        (ux, uy) = arr[l]
        (vx, vy) = arr[l + d]
        score += (abs(vx - ux) + abs(vy - uy))
        result[i].append(score)
        l += d


for l, r in lr:
    ans = result[l % d]
    print(ans[r // d] - ans[l // d])

Solution (Python):
h, w, d = map(int, input().split())
arr = [0] * (h * w + 1)

a = [list(map(int, input().split())) for _ in range(h)]

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

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

cnt = h * w
result = [[0] for _ in range(d)]
for i in range(d):
    l = i
    score = 0
    while l + d <= cnt:
        if l == 0:
            result[i].append(score)
            l += d
            continue
        (ux, uy) = arr[l]
        (vx, vy) = arr[l + d]
        score += (abs(vx - ux) + abs(vy - uy))
        result[i].append(score)
        l += d


for l, r in lr:
    ans = result[l % d]
    print(ans[r // d] - ans[l // d])

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

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

for r in range(h):
    for c in range(w):
        place[a[r][c]]=(r,c)

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


for r in range(1,w*h+1):
    if r-d<1:
        continue

    r1,c1=place[r-d]
    r2,c2=place[r]

    dp[r]=dp[r-d]+abs(r1-r2)+abs(c1-c2)

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

    print(dp[r]-dp[l])

Solution (Python):
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

h,w,d=nii()

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

b_dict={}
for i in range(1,d+1):
  num=i
  cy,cx=a_dict[num]
  b_dict[num]=0
  while num+d<=h*w:
    num+=d
    ny,nx=a_dict[num]
    b_dict[num]=b_dict[num-d]+abs(cy-ny)+abs(cx-nx)
    cy=ny
    cx=nx

q=int(input())
for i in range(q):
  l,r=nii()
  ans=b_dict[r]-b_dict[l]
  print(ans)

Solution (Python):
h,w,D = map(int,input().split())
a=[]

for _ in range(h):
    b=list(map(int,input().split()))
    a.append(b)

d={}
for i in range(h):
    c=a[i]
    for j in range(w):
        d[c[j]]=(i+1,j+1)


R_min=h*w
R_max=1
query=[]
q=int(input())
for _ in range(q):
    l,r=map(int,input().split())
    query.append([l,r])
    R_min = min(l,R_min)
    R_max = max(r,R_max)


cum=[0]*(h*w+1)
for k in range(R_min,R_max-D+1):
    prev = cum[k-1]
    cost = abs(d[k+D][0]-d[k][0]) + abs(d[k+D][1]-d[k][1])
    cum[k+D-1]=cost+prev



for j in range(q):
    l,r=query[j][0],query[j][1]
    score = cum[r-1]-cum[l-1]
    print(score)

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

H, W, D = mapint()
As = [list(mapint()) for _ in range(H)]

points = [0]*(H*W)
for i in range(H):
    for j in range(W):
        points[As[i][j]-1] = (i, j)
from collections import defaultdict
from itertools import accumulate
dic = defaultdict(list)

for i in range(1, D+1):
    h, w = points[i-1]
    cnt = 0
    while i+cnt*D<=H*W:
        h2, w2 = points[i+cnt*D-1]
        dic[i].append(abs(h2-h)+abs(w2-w))
        h, w = h2, w2
        cnt += 1
    dic[i] = list(accumulate(dic[i]))

Q = int(input())
for _ in range(Q):
    L, R = mapint()
    base = L%D
    if base==0:
        base = D
    l = (L-base)//D
    r = (R-base)//D
    print(dic[base][r]-dic[base][l])

Solution (Python):
H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
C = {i:0 for i in range(1,H*W+1)}
for i in range(H):
    for j in range(W):
        C[A[i][j]] = (i,j)
dist = {i:[] for i in range(1,D+1)}
for i in range(1,D+1):
    dist[i].append(0)
    y0,x0 = C[i]
    for j in range(1,(H*W-i)//D+1):
        y1,x1 = C[i+j*D]
        dist[i].append(dist[i][-1]+abs(y1-y0)+abs(x1-x0))
        y0 = y1
        x0 = x1
Q = int(input())
for _ in range(Q):
    L,R = map(int,input().split())
    i = L%D
    if i==0:
        i = D
    j1 = (L-i)//D
    j2 = (R-i)//D
    print(dist[i][j2]-dist[i][j1])

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

inf = 1 << 30

pos = [(0, 0)] * (h * w + 1)
dist = [inf] * (h * w + 1)

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

for i in range(1, h * w):
    if dist[i] == inf:
        dist[i] = 0
        j = i + d
        while j <= h * w:
            dist[j] = dist[j - d] + abs(pos[j][0] - pos[j - d][0]) + \
                abs(pos[j][1] - pos[j - d][1])
            j += d


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

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

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

dd = []
for i in range(d):
    csum = 0
    cumsum = []
    prev = v_to_xy[i]
    for j in range(i,h*w+1,d):
        if j == 0:
            cumsum.append(0)
            continue
        x,y = v_to_xy[j]
        diff = abs(prev[0]-x) + abs(prev[1]-y)
        csum += diff
        cumsum.append(csum)
        prev = (x,y)
    dd.append(cumsum)
    


ansl = []
for _ in range(int(input())):
    l,r = map(int, input().split())
    drem = r%d
    ri = (r-drem)//d
    li = (l-drem)//d
    
    ans = dd[drem][ri] - dd[drem][li]
    ansl.append(ans)

for ans in ansl: print(ans)

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

for h in range(H):
    A.append(list(map(int,input().split())))

pos= {}
for h in range(H):
    for w in range(W):
        pos[A[h][w]]=[h,w]

S=[0]*(H*W)
for d in range(D):
    tmp=0
    now=d+1
    while now+D<=H*W:
        nowh,noww=pos[now]
        newh,neww=pos[now+D]
        tmp+=abs(nowh-newh)+abs(noww-neww)
        S[now+D-1]=tmp
        now+=D

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

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

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

routes = [[] for _ in range(D)]
for h in range(1, H+1):
    for w in range(1, W+1):
        
        routes[A[h][w]%D].append((A[h][w], h, w))
        

Q = int(input())
costs = [[0] for _ in range(D)]
for d in range(D):
    routes[d].sort()
    
    for i in range(1, len(routes[d])):
        v1, h1, w1 = routes[d][i-1]
        v2, h2, w2 = routes[d][i]
        costs[d].append(costs[d][i-1] + abs(h1-h2)+abs(w1-w2))

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

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

d = [0] * (H * W + 1)
for i in range(1, H * W + 1):
  if i > D:
    d[i] = d[i - D] + abs(x[i][0] - x[i - D][0]) + abs(x[i][1] - x[i - D][1])


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

Solution (Python):
def main():
    H, W, D = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    B = [[] for _ in range(H * W + 1)]
    for h in range(H):
        for w in range(W):
            B[A[h][w]] = (h,w)
    C = []
    for d in range(1,D+1):
        tmp = []
        x, y = B[d]
        pre = 0
        while d <= H * W:
            nx, ny = B[d]
            now = abs(nx - x) + abs(ny - y) + pre
            tmp.append(now)
            pre = now
            x, y = nx, ny
            d += D
        C.append(tmp)
    Q = int(input())
    for _ in range(Q):
        L, R = map(int, input().split())
        index = L % D
        index -= 1
        cnt = L // D
        if L % D == 0:
            cnt -= 1
        ans = C[index][cnt + (R - L) // D] - C[index][cnt]
        print(ans)



if __name__ == "__main__":
    main()

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H,W,D = map(int,readline().split())
X = [(0,0) for _ in range(H*W)]
Y = [0 for _ in range(H*W)]

for i in range(H):
    A = [int(x)-1 for x in readline().split()]
    for j in range(W):
        X[A[j]] = (i,j)

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

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

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

for h in range(H):
  A = list(map(int,input().split()))
  for w in range(W):
    P[A[w]] = [h,w]

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

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

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

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

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

G=[[0]*((H*W+D-1)//D) for _ in range(D)]

for i in range(H*W-D):
    (X1,Y1)=L[i]
    (X2,Y2)=L[i+D]

    p,q=i//D,i%D
    G[q][p+1]=G[q][p]+abs(X1-X2)+abs(Y1-Y2)

Q=int(input())
X=[0]*Q

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

    p,r=L//D,L%D
    q=R//D
    X[k]=G[r][q]-G[r][p]

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

Solution (Python):
H, W, D = map(int, input().split())
Aindex = [0] * (H*W)
for h in range(H):
    w = 0
    for A in input().split():
        Aindex[int(A)-1] = (h,w)
        w += 1 

import numpy as np
v, h = int(np.ceil(H*W/D)), D
Mp = np.zeros((v, h), dtype='int64') 
mp = lambda X, Y: abs(X[0]-Y[0]) + abs(X[1]-Y[1]) 
for x in range(D,H*W):
    i, j = divmod(x, D)
    Mp[i,j] = mp(Aindex[x], Aindex[x-D])

Mp = Mp.cumsum(axis=0)


Q = int(input())
Query = [tuple(map(int, input().split())) for _ in range(Q)]
for l,r in Query:
    ans = Mp[divmod(r-1, D)] - Mp[divmod(l-1, D)]
    print(ans)

Solution (Python):
H, W, D = map(int, input().split())
Aindex = [0] * (H*W)
for h in range(H):
    w = 0
    for A in input().split():
        Aindex[int(A)-1] = (h,w)
        w += 1 

import numpy as np
v, h = int(np.ceil(H*W/D)), D
Mp = np.zeros((v, h)) 
mp = lambda X, Y: abs(X[0]-Y[0]) + abs(X[1]-Y[1]) 
for x in range(D,H*W):
    i, j = divmod(x, D)
    Mp[i,j] = mp(Aindex[x], Aindex[x-D])

Mp = Mp.cumsum(axis=0)


Q = int(input())
Query = [(int(x) for x in input().split()) for _ in range(Q)]
for l, r in Query:
    ans = Mp[divmod(r-1, D)] - Mp[divmod(l-1,D)]
    print(int(ans))

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

x_axis = [0]*(H*W)
y_axis = [0]*(H*W)

for i in range(H):
  A = list(map(lambda x: int(x)-1, input().split()))
  for j in range(W):
    x_axis[A[j]] = j
    y_axis[A[j]] = i

def dis(a, b):
  return abs(x_axis[a]-x_axis[b]) + abs(y_axis[a]-y_axis[b])

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

for i in range(D):
  temp = i
  while temp < H*W-D:
    magic[i].append(magic[i][-1] + dis(temp, temp+D))
    temp += D

Q = int(input())
for _ in range(Q):
  L, R = map(lambda x: int(x)-1, input().split())
  L, d = divmod(L, D)
  R //= D
  print(magic[d][R] - magic[d][L])

Solution (Python):
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
inv_A = [(0, 0)] * (H*W+1)
for y, a in enumerate(A):
    for x, a_ in enumerate(a):
        inv_A[a_] = (y, x)
C = [0] * D
c = 0
for i in range(D, H*W+1):
    y1, x1 = inv_A[i]
    y2, x2 = inv_A[i-D]
    C.append(abs(y1-y2)+abs(x1-x2)+C[i-D])
Ans = []
Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    Ans.append(C[r]-C[l])
print("\n".join(map(str, Ans)))

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

G = [(-10**9, -10**9) for _ in range(H * W + 1)]

for i in range(H):
    line = list(map(int, input().split()))
    for j in range(W):
        grid = int(line[j])
        G[grid] = (i, j)


cost = [0 for _ in range(H * W + 1)]
for i in range(D + 1, H * W + 1):
    cost_x = abs(G[i][0] - G[i - D][0])
    cost_y = abs(G[i][1] - G[i - D][1])
    cost[i] = cost[i - D] + cost_x + cost_y

ans = []

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




for i in ans:
    print(i)

Solution (Python):
def get_dist(cur, nxt):
    return abs(cur[0] - nxt[0]) + abs(cur[1] - nxt[1])


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

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

acc = [0] * (H * W + 1)
for i in range(D + 1, H * W + 1):
    acc[i] = acc[i - D] + get_dist(pos[i - D], pos[i])

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

Solution (Python):
from itertools import accumulate


def get_dist(cur, nxt):
    return abs(cur[0] - nxt[0]) + abs(cur[1] - nxt[1])


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

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

acc = []
for i in range(D):
    res = [0]
    now = i
    while now + D < H * W:
        nxt = now + D
        res.append(get_dist(pos[now], pos[nxt]))
        now = nxt
    acc.append(list(accumulate(res)))

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

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

lis=[[] for i in range(h*w)]
for i in range(h):
  ai=list(map(int,input().split()))
  for j in range(w):
    lis[ai[j]-1].append(i)
    lis[ai[j]-1].append(j)

U=[]

for i in range(d):
  Ui=[0]
  j=1
  while i+j*d<h*w:
    Ui.append(Ui[j-1]+abs(lis[i+j*d][0]-lis[i+(j-1)*d][0])
              +abs(lis[i+j*d][1]-lis[i+(j-1)*d][1]))
    j+=1
  U.append(Ui)

q=int(input())


for i in range(q):
  li,ri=map(lambda x:int(x)-1,input().split())
  modi=li%d
  print(U[modi][(ri-modi)//d]-U[modi][(li-modi)//d])

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

for i in range(d):
    a[i]=0
    tmp=0
    while i<h*w-d :
        ni=i+d
        t=abs(basyo[i][0][0]-basyo[ni][0][0])+abs(basyo[i][0][1]-basyo[ni][0][1])
        tmp+=t
        a[ni]=tmp
        i=ni
q=int(input())
for i in range(q):
    x,y=map(int,input().split())
    x,y=x-1,y-1
    print(a[y]-a[x])

Solution (Python):
from collections import defaultdict
H,W,D = map(int,input().split())
grid = [[0]*W for _ in range(H)]
for h in range(H):
    grid[h] = list(map(int, input().split()))
number_yx = [[0,0] for _ in range(H*W+1)]
for y in range(H):
    for x in range(W):
        number_yx[grid[y][x]] = [y,x]
fromto_cost = defaultdict(lambda: defaultdict(int))
for mod_group in range(D):
    
    start = mod_group+1
    previous = start
    fromto_cost[start][start] = 0
    previous_y, previous_x = number_yx[previous]
    cost = 0
    while previous+D <= (H*W):
        Next = previous+D 
        Next_y, Next_x = number_yx[Next]
        cost += abs(Next_y-previous_y) + abs(Next_x-previous_x)
        fromto_cost[start][Next] = cost

        previous = Next
        previous_y,previous_x = Next_y,Next_x

Q = int(input())
ans_ls = [0] * Q
for i in range(Q):
    start, goal = map(int,input().split())
    mod = start % D
    base = mod
    if base == 0:
        base = D 
    base_to_goal = fromto_cost[base][goal]
    base_to_start = fromto_cost[base][start]
    ans_ls[i] = base_to_goal - base_to_start
for ans in ans_ls:
    print(ans)