Problem:
 Score : 400 points    Problem Statement We have a grid with H rows and W columns. The square at the i -th row and the j -th column will be called Square (i,j) .  The integers from 1 through H×W are written throughout the grid, and the integer written in Square (i,j) is A_{i,j} .  You, a magical girl, can teleport a piece placed on Square (i,j) to Square (x,y) by consuming |x-i|+|y-j| magic points.  You now have to take Q practical tests of your ability as a magical girl.  The i -th test will be conducted as follows:    Initially, a piece is placed on the square where the integer L_i is written.    Let x be the integer written in the square occupied by the piece. Repeatedly move the piece to the square where the integer x+D is written, as long as x is not R_i . The test ends when x=R_i .    Here, it is guaranteed that R_i-L_i is a multiple of D .    For each test, find the sum of magic points consumed during that test.      Constraints  1 \leq H,W \leq 300  1 \leq D \leq H×W  1 \leq A_{i,j} \leq H×W  A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))  1 \leq Q \leq 10^5  1 \leq L_i \leq R_i \leq H×W  (R_i-L_i) is a multiple of D .         Input Input is given from Standard Input in the following format:  H  W  D  A_{1,1}  A_{1,2}  ...  A_{1,W}  :  A_{H,1}  A_{H,2}  ...  A_{H,W}  Q  L_1  R_1  :  L_Q  R_Q       Output For each test, print the sum of magic points consumed during that test.  Output should be in the order the tests are conducted.        Sample Input 1 3 3 2
1 4 3
2 5 7
8 9 6
1
4 8      Sample Output 1 5    4 is written in Square (1,2) .    6 is written in Square (3,3) .    8 is written in Square (3,1) .    Thus, the sum of magic points consumed during the first test is (|3-1|+|3-2|)+(|3-3|+|1-3|)=5 .       Sample Input 2 4 2 3
3 7
1 4
5 2
6 8
2
2 2
2 2      Sample Output 2 0
0  Note that there may be a test where the piece is not moved at all, and there may be multiple identical tests.       Sample Input 3 5 5 4
13 25 7 15 17
16 22 20 2 9
14 11 12 1 19
10 6 23 8 18
3 21 5 24 4
3
13 13
2 10
13 13      Sample Output 3 0
5
0

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

h,w,d=MI()
mp=[LI() for i in range(h)]
lis=[[0,0] for i in range(w*h)]
for i in range(h):
    for j in range(w):
        lis[mp[i][j]-1]=[i,j]


costs=[0 for i in range(h*w+1)]
for i in range(1,d+1):
    for j in range(0,h*w):
        if i+d*(j+1)<h*w+1:
            costs[i+d*(j+1)]=costs[i+d*j]+abs(lis[i+d*(j+1)-1][1]-lis[i+d*j-1][1])+abs(lis[i+d*(j+1)-1][0]-lis[i+d*j-1][0])
        else:
            break
q=I()
for i in range(q):
    l,r=MI()
    u=l%d
    print(costs[r]-costs[l])

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

def main():
    h, w, d = map(int, input().split())

    x = [0] * (h*w)
    y = x.copy()
    for i in range(h):
        a = list(map(int, input().split()))
        for j in range(w):
            x[a[j] - 1] = i
            y[a[j] - 1] = j

    
    cost = [[0] for _ in range(d)]
    for i in range(d, h*w):
        cost[i%d].append(cost[i%d][-1] + abs(x[i]-x[i-d]) + abs(y[i]-y[i-d]))

    ans = []
    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        l -= 1
        r -= 1
        ans.append(cost[r%d][r//d] - cost[l%d][l//d])

    for i in ans:
        print(i)

main()

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

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

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

for i in range(h):
    for j in range(w):
        s = ab[i][j]
        dp[s] =[i,j]
        
dpp= [0]*(h*w+1)

for k in range(d+1,h*w+1):

    dpp[k] = dpp[k-d] + abs(dp[k][0]-dp[k-d][0]) +abs(dp[k][1]-dp[k-d][1])
    
q = int(input())

for x in range(q):
    a,b = map(int, input().split())
    print(dpp[b]-dpp[a])

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

def main():
    h, w, d = map(int, input().split())

    x = [0] * (h*w)
    y = x.copy()
    for i in range(h):
        a = list(map(int, input().split()))
        for j in range(w):
            x[a[j] - 1] = i
            y[a[j] - 1] = j

    
    cost = [[0] for _ in range(d)]
    for i in range(d, h*w):
        cost[i%d].append(cost[i%d][-1] + abs(x[i]-x[i-d]) + abs(y[i]-y[i-d]))

    ans = []
    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        l -= 1
        r -= 1
        ans.append(cost[r%d][r//d] - cost[l%d][l//d])

    for i in ans:
        print(i)

main()

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

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

  B=[0]*(H*W)
  for i in range(H*W-D):
    B[i+D]=B[i]+abs(A[i][0]-A[i+D][0])+abs(A[i][1]-A[i+D][1])

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

main()

Solution (Python):
def main():
  H,W,D=map(int,input().split())
  A=[]
  for h in range(H):
    for w,a in enumerate(map(int,input().split())):
      A+=[[a,h,w]]
  A.sort(key=lambda x:x[0])

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

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

main()

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

def main():
  A=list()
  for h in range(H):
    for w,a in enumerate(map(int,input().split())):
      A.append([a,h,w])

  A=sorted(A, key=lambda x:x[0])

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

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

main()

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

for i in ans:
    print(i)

Solution (Python):
h,w,d=map(int,input().split())
l=[[] for t in range(h*w)]
for i in range(h):
  ll=list(map(int,input().split()))
  for j in range(w):
    l[ll[j]-1]=[i,j]
    
r=[[0] for dd in range(d)]
for dd in range(d):
  if dd==0:
    k=d
  else:
    k=dd
  while k+d<=h*w:
    r[dd].append(r[dd][-1]+abs(l[k+d-1][0]-l[k-1][0])+abs(l[k+d-1][1]-l[k-1][1]))
    k+=d

    
q=int(input())
for qq in range(q):
  a,b=map(int,input().split())
  if a%d==0:
    p=d
  else:
    p=a%d
  aa=(a-p)//d
  bb=(b-p)//d
  ans=r[a%d][bb]-r[a%d][aa]
  print(ans)

Solution (Python):
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from collections import defaultdict
    from itertools import accumulate

    h, w, d = map(int, readline().split())
    dict = defaultdict(list)
    memo = [[0] for _ in range(d + 1)]
    for i in range(h):
        a = list(map(int, readline().split()))
        for j, aa in enumerate(a):
            dict[aa] = [i, j]
    for i in range(1, d + 1):
        bf = i
        for af in range(i + d, h * w + 1, d):
            memo[i].append(abs(dict[bf][0] - dict[af][0]) + abs(dict[bf][1] - dict[af][1]))
            bf = af
        memo[i] = list(accumulate(memo[i]))
    q = int(readline())
    for _ in range(q):
        l, r = map(int, readline().split())
        if r < l:
            r, l = l, r
        l, i = divmod(l, d)
        r //= d
        if i == 0:
            i = d
            l -= 1
            r -= 1
        print(memo[i][r] - memo[i][l])


if __name__ == '__main__':
    main()

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  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 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)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





H,W,D = IL()
posx = [None for i in range(H*W)]
posy = [None for i in range(H*W)]

for i in range(H):
  L = IL()
  for j in range(W):
    posx[L[j]-1] = i
    posy[L[j]-1] = j
    
DIC = DD(lambda : [0])

for x in range(D,H*W):
  i = x%D
  DIC[i].append(DIC[i][-1]+abs(posx[x]-posx[x-D])+abs(posy[x]-posy[x-D]))
  
Q = I()
for _ in range(Q):
  L,R = IL()
  L,R = L-1,R-1
  i = L%D
  s = L//D
  t = R//D
  print(DIC[i][t]-DIC[i][s])

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  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 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)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





H,W,D = IL()
posx = [None for i in range(H*W)]
posy = [None for i in range(H*W)]

for i in range(H):
  L = IL()
  for j in range(W):
    posx[L[j]-1] = i
    posy[L[j]-1] = j
    
DICX = DD(lambda : [0])
DICY = DD(lambda : [0])

for x in range(D,H*W):
  i = x%D
  DICX[i].append(DICX[i][-1]+abs(posx[x]-posx[x-D]))
  DICY[i].append(DICY[i][-1]+abs(posy[x]-posy[x-D]))

Q = I()
for _ in range(Q):
  L,R = IL()
  L,R = L-1,R-1
  i = L%D
  s = L//D
  t = R//D
  print((DICX[i][t]-DICX[i][s])+(DICY[i][t]-DICY[i][s]))

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)]
dmap={}
for hi in range(h):
  for wi in range(w):
    dmap[a[hi][wi]-1]=(hi+1,wi+1)
dans={}
for di in range(d):
  s=di
  x,y=dmap[di]
  tmp=0
  while s<h*w:
    nx,ny=dmap[s]
    tmp+=abs(x-nx)+abs(y-ny)
    dans[(di,s)]=tmp
    x,y=nx,ny
    s+=d
for l,r in lr:
  l-=1;r-=1
  s=l%d
  print(dans[(s,r)]-dans[(s,l)])

Solution (Python):


H, W, D = map(int, input().split())
MAX = H * W + 1

d = [0] * (MAX + 1)
px = [None] * (MAX + 1)
py = [None] * (MAX + 1)

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

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):
h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]

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

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

for i in range(1,d+1):
    a = 0
    rui[i] = 0
    for j in range(i+d,h*w+1,d):
        a += (abs(iti[j][0] - iti[j-d][0]) + abs(iti[j][1] - iti[j-d][1]))
        rui[j] = a

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

Solution (Python):
from collections import defaultdict
import itertools
d = defaultdict(int)
x='MARCH'
for i in range(5):
  d[x[i]]=i+1
x=[0]*5
def sub(a,b):
  return abs(a[0]-b[0])+abs(a[1]-b[1])

H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
N=H*W
P=[0]*(N)
for h in range(H):
  for w in range(W):
    P[A[h][w]-1]=(h,w)
X=[]
for d in range(D):
  _=[0]+[sub(P[i%N],P[i-D]) for i in range(d+D,N+D,D)]
  cumsum = list(itertools.accumulate(_))
  X.append(cumsum)

Q=int(input())
for q in range(Q):
  l,r=map(int,input().split())
  l,r=l-1,r-1
  g=l%D
  if l>r:
    r+=N
    ans=X[g][-1]-X[g][l//D]
    ans+=X[g][r//D]-X[g][0]
  else:
    ans=X[g][r//D]-X[g][l//D]
  
  print(ans)

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

a={}
for y in range(h):
    tmp=list(map(int,input().split()))

    for x,v in enumerate(tmp):
        a[v]=(y,x)

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



for i in range(1,h*w+1):
    if i>d:
        bk=a[i-d]
        nx=a[i]
        dis[i]=dis[i-d]+abs(bk[0]-nx[0])+abs(bk[1]-nx[1])

q=int(input())
ans=[]
for _ in range(q):
    start,goal=map(int,input().split())
    ans.append(dis[goal]-dis[start])

for item in ans:
    print(item)

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

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

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

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

Solution (Python):
h,w,d= map(int, input().split())
a = {}
for y in range(h):
    line = list(map(int, input().split()))
    for x in range(len(line)):
        a[line[x]-1] = (y,x)









num = len(a)
dp = [0]*num
for i in range(num-1, -1, -1):
    if i+d <= num-1:
        x, y = a[i]
        px, py = a[i+d]
        dp[i] = dp[i+d] + abs(x-px) + abs(y-py)

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

Solution (Python):
h,w,d = map(int, input().split())
ad = {}
for i in range(h):
    line = list(map(int, input().split()))
    for j in range(w):
        ad[line[j]] = (i,j)
q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]

cl = [0]*(h*w+1)
for i in range(1,h*w+1):
    if i+d<len(cl):
        f = ad[i]
        t = ad[i+d]
        cl[i+d] = cl[i] + abs(f[0]-t[0]) + abs(f[1]-t[1])

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

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

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





cost = [0]*(H*W+1)
for i in range(1,D+1):
    num = i
    now = None
    while True:
        if num > H*W:
            break
        for row in range(H):
            if num in Aset[row]:
                
                ind = A[row].index(num)
                if now == None:
                    now = (ind, row)
                    cost[num] = 0
                else:
                    cost[num] = cost[num-D] + abs(ind-now[0]) + abs(row-now[1])
                    now = (ind, row)
        num += D

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

Solution (Python):
def resolve():
    H, W, D = list(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)]

    num_to_pos = {}
    for i in range(H):
        for j in range(W):
            num_to_pos[A[i][j]] = (i, j)
    
    acc = [[0] for _ in range(D+1)]
    for i in range(1, D+1):
        num = i
        idx = 0
        while num + D <= H*W:
            _from = num_to_pos[num]
            _to = num_to_pos[num+D]
            acc[i].append(acc[i][idx]+abs(_from[0]-_to[0])+abs(_from[1]-_to[1]))
            num += D
            idx += 1
    
    
    for lr in LR:
        l, r = lr
        series = l%D if l%D != 0 else D
        
        
        
        print(acc[series][(r-series)//D] - acc[series][(l-series)//D])
            



if '__main__' == __name__:
    resolve()

Solution (Python):
from collections import deque
h , w , d = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
zahyo = [-1 for i in range(h*w+1)]
for i in range(h):
    for j in range(w):
        zahyo[a[i][j]] = (a[i][j],i,j)
ans = [-1 for i in range(h*w + 1)]
for i in range(1,h*w+1):
    if ans[i] == -1:
        ans[i] = 0
        p = deque()
        p.append(zahyo[i])
        while p:
            now , nowx , nowy = p.popleft()
            if now + d > h*w:
                break
            tugi , nexx , nexy = zahyo[now+d]
            p.append(zahyo[now+d])
            ans[tugi] = ans[now] + abs(nowx-nexx) + abs(nowy-nexy)

    else:
        continue

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

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

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

dis = [0] * (h*w + 1)
for i in range(h*w+1):
    if i > d:
        x1, y1 = pos[i-d]
        x2, y2 = pos[i]
        dis[i] = abs(x1-x2) + abs(y1-y2) + dis[i-d]

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

    res.append(dis[r]-dis[l])

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

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    def calc_cost(cur, prev):
        return abs(cur[0] - prev[0]) + abs(cur[1] - prev[1])

    h, w, d = map(int, readline().split())
    a = [list(map(int, readline().split())) for _ in range(h)]
    q = int(readline())
    coordinate = dict()

    for row in range(h):
        for col in range(w):
            num = a[row][col]
            coordinate[num] = (row, col)

    cost = dict()

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

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


if __name__ == '__main__':
    main()

Solution (Python):
h, w, d = map(int, input().split())
n = h*w
paths = [[]for _ in range(d)]
for i in range(n):
    paths[i % d].append(i)


class P:
    def __init__(self, x, y):
        self.x, self.y = x, y

    def __sub__(self, p):
        return P(self.x-p.x, self.y-p.y)

    def _abs(self):
        return P(abs(self.x), abs(self.y))

    def _sum(self):
        return self.x+self.y

    def to(self, p):
        return (self-p)._abs()._sum()


coodinates = [None]*n
for i in range(h):
    for j, a in enumerate(map(lambda x: int(x)-1, input().split())):
        coodinates[a] = P(i, j)

costs = [[0]for _ in range(d)]
for i in range(d):
    for x, y in zip(paths[i], paths[i][1:]):
        p, q = coodinates[x], coodinates[y]
        costs[i].append(costs[i][-1]+p.to(q))

q = int(input())
for _ in range(q):
    L, R = map(lambda x: int(x)-1, input().split())
    print(costs[L % d][R//d]-costs[L % d][L//d])

Solution (Python):



import numpy
from collections import defaultdict

def main():
  h, w, d = map(int, input().split())
  mat_a = numpy.array([list(map(int, input().split())) for _ in range(h)])
  q = int(input())
  x_to_pos = dict()
  
  for i in range(h):
    for j in range(w):
      x_to_pos[mat_a[i, j]] = (i, j)
      
  def calc_score(p1, p2):
    return sum([abs(x-y) for x, y in zip(p1, p2)])
  
  visited = numpy.zeros((h, w))
  costs = defaultdict(dict)
  for c in range(1, d+1):
    cost = 0
    costs[c%d][c] = 0
    while True:
      cp = x_to_pos[c]
      c += d
      if c > (h*w):
        break
      np = x_to_pos[c]
      cost += calc_score(cp, np)
      costs[c%d][c] = cost
  
  for _ in range(q):
    l, r = map(int, input().split())
    print(abs(costs[l%d][l] - costs[l%d][r]))

if __name__=='__main__':
  main()

Solution (Python):
from collections import deque
H, W, D = map(int, input().split())
mod_dict = [deque() for _ in range(D)]
h = 0
while h < H:
  A = list(map(int, input().split()))
  w = 0
  while w < W:
    a = A[w]
    mod_dict[a%D].append((a, h, w))
    w += 1
  h += 1
ruiseki_dict = [deque() for _ in range(D)]
d = 0
while d < D:
  m = sorted(mod_dict[d], key=lambda x:x[0])
  py, px = m[0][1], m[0][2]
  ruiseki_dict[d].append(0)
  i = 0 if d == 0 else 1
  while i < len(m):
    ry, rx = m[i][1], m[i][2]
    ruiseki_dict[d].append(ruiseki_dict[d][-1]+abs(ry-py)+abs(rx-px))
    py, px = ry, rx
    i += 1
  d += 1
Q = int(input())
for _ in range(Q):
  l, r = list(map(int, input().split()))
  d = ruiseki_dict[r%D]
  print(d[r//D]-d[l//D])

Solution (Python):






from collections import deque





h,w,d=map(int,input().split())
dic={i:0 for i in range(1,h*w+1)}
for i in range(h):
    l=list(map(int,input().split()))
    for j in range(w):
        dic[l[j]]=(i+1,j+1)
q=int(input())
lr = [list(map(int,input().split())) for _ in range(q)]
res=[[] for _ in range(d)]
for i in range(1,h*w-d+1):
    x,y=dic[i]
    s,t=dic[i+d]
    power=abs(x-s)+abs(y-t)
    res[i%d].append(power)
for i in range(d):
    length=len(res[i])
    x=0
    for j in range(length):
        x+=res[i][j]
        res[i][j]=x
for i in range(q):
    l,r=lr[i]
    if l==r:
        print(0)
        continue
    else:
        mod=l%d
        quol=l//d
        quor=r//d-1
        if mod==0:
          quol-=1
          quor-=1
        if quol==0:
          print(res[mod][quor])
        else:
          quol-=1
          print(res[mod][quor]-res[mod][quol])

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

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

route = [0] * (H * W + 1)
for i in range(H):
  line = list(map(int,readline().split()))
  for j in range(len(line)):
    route[line[j]] = (i,j)




dist = [0] * (H * W + 1)
for i in range(D + 1,len(route)):
  gy,gx = route[i]
  sy,sx = route[i - D]
  dist[i] = abs(gy - sy) + abs(gx - sx) 
  dist[i] = dist[i] + dist[i - D]


Q = int(readline())

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

Solution (Python):
h, w, d = [int(x) for x in input().split()]
n = h * w

p_list = [None] * (n + 1)
for i in range(h):
    a_list = [int(x) for x in input().split()]
    for j in range(w):
        p_list[a_list[j]] = (i, j)

m_a_list = [0] * (n + 1)
for start in range(1, d + 1):
    p_i, p_j = p_list[start]
    p_target = start
    for target in range(start + d, n + 1, d):
        n_i, n_j = p_list[target]
        m = abs(n_i - p_i) + abs(n_j - p_j)
        m_a_list[target] = m + m_a_list[p_target]
        p_i, p_j, p_target = n_i, n_j, target

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

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

mat_map = [()]*(h*w+1)

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

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

for i in range(h*w-1, 0, -1):
    if i+d > h*w:
        continue
    current = mat_map[i]
    nex = mat_map[i+d]
    dist = abs(current[0]-nex[0]) + abs(current[1]-nex[1])
    dp[i] = dp[i+d] + dist

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

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

Solution (Python):
import sys
import itertools

input = sys.stdin.readline

def myindex(l, element, default=-1):
    if element in set(l):
        return l.index(element)
    else:
        return default

def main():
    H, W, D = map(int, input().split())
    grid = []; locale = [0]*(H*W)
    for i in range(H):
        tmp = list(map(int, input().split()))
        for j, t in enumerate(tmp):
            x, y = i+1, j+1
            locale[t-1] = (x, y)
        grid.append(tmp)
    
    power = []
    for k in range(H*W-D):
        fr = locale[k]
        to = locale[k+D]
        need = abs(fr[0]- to[0]) + abs(fr[1] - to[1])
        power.append(need)
    
    cum = []
    for d in range(D):
        cum.append([0] + list(itertools.accumulate(power[d::D])))

    Q = int(input())
    for _ in range(Q):
        L, R = map(int, input().split())
        d = (L-1)%D
        dnum = (L-1)//D
        drange = (R-L)//D
        ans = cum[d][dnum+drange] - cum[d][dnum]
        print(ans)
    
if __name__ == "__main__":
    main()

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

cords = [0] * (h*w+1)
for i in range(h):
    line = tuple(map(int, input().split()))
    for j in range(w):
        cords[line[j]] = (i, j)


acccosts = [0] * (h*w+1)
for num in range(1, h*w+1-d):
    nxy = cords[num]
    nnxy = cords[num+d]
    acccosts[num+d] = acccosts[num] + abs(nxy[0]-nnxy[0]) + abs(nxy[1] - nnxy[1])

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

Solution (Python):
h,w,d=map(int,input().split())
ind={}
for i in range(h):
    l=list(map(int,input().split()))

    for j in range(w):
        ind[l[j]]=(i,j)
dp=[0]*(h*w)
for i in range(d+1,h*w+1):
    x,y=ind[i]
    z,q=ind[i-d]
    dp[i-1]=abs(z-x)+abs(y-q)+dp[i-d-1]


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

Solution (Python):
h,w,d=map(int,input().split())
ind={}
for i in range(h):
    l=list(map(int,input().split()))

    for j in range(w):
        ind[l[j]]=(i,j)
table=[0]*((((h*w)//d).bit_length())*h*w)
now=1
for i in range(1,h*w-d+1):
    a,s=ind[i]
    de,f=ind[i+d]
    table[i-1+d]=abs(a-de)+abs(s-f)
step=2
for i in range(1,((h*w)//d).bit_length()):
    for j in range(1,h*w-step*d+1):
        table[j-1+step*d+i*h*w]=table[j-1+d*step//2+(i-1)*h*w]+table[j-1+d*step+(i-1)*h*w]
    step*=2

q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    times=(r-l)//d
    cost=0
    now=1
    kata=0
    while times:
        if times%2:
            l+=d*now
            cost+=table[l-1+kata*h*w]

        times//=2
        now*=2
        kata+=1
    print(cost)