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
h,w,d=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(h)]
x=[0]*(h*w+1)
y=[0]*(h*w+1)
for i in range(1,h+1):
    for j in range(1,w+1):
        x[a[i-1][j-1]]=i
        y[a[i-1][j-1]]=j
dp=[0]*(h*w+1)
for i in range(d+1,h*w+1):
    dp[i]=dp[i-d]+abs(x[i]-x[i-d])+abs(y[i]-y[i-d])

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

Solution (Python):
import collections
def main():
    H, W, D = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(list(map(int, input().split())))
    Q = int(input())
    queries = []
    for _ in range(Q):
        L, R = map(int, input().split())
        queries.append([L, R])

    d = collections.defaultdict(list)
    for i in range(H):
        for j in range(W):
            d[A[i][j] % D].append([A[i][j], i, j])
    for v in d:
        d[v] = sorted(d[v], key = lambda x: x[0])

    d1 = collections.defaultdict(list)
    for v in d:
        prefix = [0]
        if v == 0:
            prefix.append(0)
        for i in range(len(d[v])-1):
            mag = abs(d[v][i][1] - d[v][i+1][1]) + abs(d[v][i][2]-d[v][i+1][2])
            prefix.append(prefix[-1]+mag)
        d1[v] = prefix
    

    
    for L, R in queries:
        if L == R:
            print(0)
        else:
            l = (R-L) // D
            i = L // D
            v = L % D
            magic = d1[v][i+l] - d1[v][i]
            print(magic)

if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    n = II()
    print(n//3)
    return


def B():
    _ = II()
    s = S()
    print(["Three", "Four"][len(set(s)) - 4])
    return


def C():
    return

class Value_UnionFind():
    def __init__(self,n):
        self.par = [i for i in range(n)]
        self.differ_weight = [0] * n
        self.rank = [0] * n

    def root(self,x):
        if x == self.par[x]:
            return x
        r = self.root(self.par[x])
        self.differ_weight[x] += self.differ_weight[self.par[x]]
        self.par[x] = r
        return r

    def weight(self, x):
        self.root(x)
        return self.differ_weight[x]

    def unit(self, x, y, w):
        w += self.weight(x)
        w -= self.weight(y)
        x = self.root(x)
        y = self.root(y)
        if x == y: return False
        if self.rank[x] < self.rank[y]: x, y, w = y, x, -w
        if self.rank[x] == self.rank[y]: self.rank[x] += 1
        self.par[y] = x
        self.differ_weight[y] = w
        return True

    def differ(self, x, y):
        return self.weight(y) - self.weight(x)

def D():
    h, w, d = LI()
    u = Value_UnionFind(h * w)
    field = defaultdict(list)
    for i in range(h):
        a = LI_()
        for j in range(w):
            field[a[j]] = [j, i]
    for i in range(h * w):
        if i + d < h * w:
            x1, y1 = field[i]
            x2, y2 = field[i + d]
            u.unit(i, i + d, abs(x1 - x2) + abs(y1 - y2))

    for _ in range(II()):
        l, r = LI_()
        print(u.differ(l, r))
    return


if __name__ == '__main__':
    D()

Solution (Python):
h, w, d = map(int, input().split())
num_dict = [[] for _ in range(h * w)]
for i in range(h):
    num_list = [int(i) for i in input().split()]
    for j, num in enumerate(num_list):
        num_dict[num - 1] = (i + 1, j + 1)
accum_list = [0 for _ in range(h * w)]
for i in range((h * w) - d - 1, -1, -1):
    accum_list[i] += (abs(num_dict[i + d][0] - num_dict[i][0]) +
                      abs(num_dict[i + d][1] - num_dict[i][1]) + accum_list[i + d])
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(accum_list[l - 1] - accum_list[r - 1])

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

Dist = [0]*(H*W+1)
for k in range(0, H*W-D+1):
  i, j = M[k]
  x, y = M[k+D]
  Dist[k+D] = Dist[k]+abs(x-i)+abs(y-j)
Q = int(input())
for i in range(Q):
  L, R = map(int, input().split())
  r = Dist[R]-Dist[L]
  print(r)

Solution (Python):
import numpy as np

h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]
q = int(input())
b = [list(map(int,input().split())) for _ in range(q)]
p =[0]*(h*w+1)
    
for i in range(h):
    for j in range(w):
        tmp = a[i][j]
        p[tmp] = [i,j]
cost = [0]*(h*w+1)
i = d+1
while i <= h*w:
    cost[i] = cost[i-d] + abs(p[i][0]-p[i-d][0]) + abs(p[i][1]-p[i-d][1])
    i += 1
for k in range(q):
    r = b[k][0]
    l = b[k][1]
    print(cost[l]-cost[r])

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

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

Q = int(input())
ANS = [0] * (H * W + 1)

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

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

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

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

place = []


for i in range(H):
    for j in range(W):
        place.append([grid[i][j], i, j])
place.sort()


classify = [[0] for i in range(D)]

for i in range(D):
    for j in range(i, H*W-D, D):
        classify[(i+1)%D].append(abs(place[j+D][1]-place[j][1])+abs(place[j+D][2]-place[j][2]) + classify[(i+1)%D][-1])

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

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

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

place = []


for i in range(H):
    for j in range(W):
        place.append([grid[i][j], i, j])
place.sort()


classify = [[0] for i in range(D)]

for i in range(D):
    for j in range(i, H*W-D, D):
        classify[(i+1)%D].append(abs(place[j+D][1]-place[j][1])+abs(place[j+D][2]-place[j][2]) + classify[(i+1)%D][-1])

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

Solution (Python):

import sys


def solve(H: int, W: int, D: int, A: "List[List[int]]", Q: int, L: "List[int]", R: "List[int]"):
    K = {}
    for i in range(H):
        for j in range(W):
            K[A[i][j]] = (i, j)
    B = [[0 for _ in range(W)] for _ in range(H)]
    for i in range(D+1, H*W+1):
        j = i % D
        ti, tj = K[i]
        si, sj = K[i-D]
        B[ti][tj] = B[si][sj] + abs(ti-si) + abs(tj-sj)
    for q in range(Q):
        ri, rj = K[R[q]]
        li, lj = K[L[q]]
        s = B[ri][rj] - B[li][lj]
        print(s)
    return



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

if __name__ == '__main__':
    main()

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

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

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

def magic(LR):
  magic = 0
  x = LR[0]
  y = LR[1]
  magicx = abs(A[x][0] - A[y][0]) 
  magicy = abs(A[x][1] - A[y][1]) 
  return magicx + magicy

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

for i in range(Q):
  x = LR[i][0]
  y = LR[i][1]
  if (x == y):
    print(0)
  else:
    print(magiclist[y]- magiclist[x])

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

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

c = [0]*d
for i in range(len((b))-d):
    c.append(abs(b[i+d][0]-b[i][0])+abs(b[i+d][1]-b[i][1])+c[-d])

q = int(input())
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())

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


memo = [0]*(H*W)
for x in range(H*W):
  if x<D:
    continue
  i,j = pos[x-D][0],pos[x-D][1]
  u,v = pos[x  ][0],pos[x  ][1]
  memo[x] = memo[x-D]+abs(i-u)+abs(j-v)

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    H, W, D = LI()
    mod_array = [[(0,0) for _ in range(H*W//D+1)] for _ in range(D)]
    for row_number in range(H):
        row = LI()
        for column_number, item in enumerate(row):
            mod_array[item%D][item//D] = (row_number, column_number)

    

    mod_array_cumsum = [[0 for _ in range(H*W//D+1)] for _ in range(D)]
    for row_number in range(D):
        cumsum = 0
        prev_position = mod_array[row_number][0]
        for column_number in range(1, H*W//D+1):
            position = mod_array[row_number][column_number]
            cumsum += abs(prev_position[0] - position[0]) + abs(prev_position[1] - position[1])
            mod_array_cumsum[row_number][column_number] = cumsum
            prev_position = position

    

    Q = II()
    for _ in range(Q):
        L, R = LI()
        ans = mod_array_cumsum[L%D][R//D] - mod_array_cumsum[L%D][L//D]
        print(ans)
        

main()

Solution (Python):
H,W,D = map(int, input().split())
fields = []
amaris = [[0] * (H*W//D+1) for i in range(D)] 
for i in range(H):
    row = list(map(int, input().split()))
    
    for j,e in enumerate(row):
        n = (e-1) // D
        m = (e-1) % D
        amaris[m][n] = (i,j)


acc = [[0] * (H*W//D+1) for i in range(D)]
for i in range(D):
    cnt = 0
    x_pre, y_pre = amaris[i][0]
    for j in range(1,(H*W)//D+1):
        coords = amaris[i][j]
        if isinstance(coords,int): break
        x = coords[0]
        y = coords[1]
        cnt += abs(x-x_pre)+abs(y-y_pre)
        acc[i][j] = cnt
        x_pre = x
        y_pre = y


Q = int(input())
for i in range(Q):
    l,r  = map(int, input().split())
    m = (l-1) % D
    s = (l-1) // D
    g = (r-1) // D
    ans = acc[m][g] - acc[m][s]
    print(ans)

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

def main():
  h, w, d = map(int, input().split())
  axy = [None for _ in range(h*w+1)]
  for y in range(h):
    for x, a in enumerate(map(int, input().split())):
      axy[a] = (x, y)

  dlist = [0 for _ in range(h*w+1)]
  for a in range(d+1, h*w+1):
    dlist[a] = dlist[a-d] + abs(axy[a][0] - axy[a-d][0]) + abs(axy[a][1] - axy[a-d][1])

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


if __name__ == '__main__':
  main()

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

place = [None]*(H*W+1)
for h in range(H):
    for w in range(W):
        place[A[h][w]] = (h, w)
place[0] = (0, 0)
dis = [[0 for _ in range((H*W)//D+1)] for _ in range(D)]
for i, (x, y) in enumerate(place):
    if i <= D:
        continue
    bx, by = place[i-D]
    dis[i%D][i//D] = dis[i%D][i//D-1] + abs(x-bx) + abs(y-by)


for l, r in LR:
    ans = dis[r%D][r//D] - dis[l%D][l//D]
    print(ans)

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

array_len = math.ceil(H*W/D)

a_array = [[[0, 0] for _ in range(array_len)] for _ in range(D)]
for i in range(H):
    A = map(int, input().split())
    for j, a in enumerate(A):
        a = a - 1
        a_array[a % D][a//D][0] = i + 1
        a_array[a % D][a//D][1] = j + 1


sum_array = [[0] * array_len for _ in range(D)]
for i in range(D):
    s = 0
    for j in range(1, array_len):
        s += (abs(a_array[i][j][0]-a_array[i][j-1][0]) +
              abs(a_array[i][j][1]-a_array[i][j-1][1]))
        sum_array[i][j] = s



Q = int(input())

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

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



query = []
q = int(input())
for i in range(q):
    query.append(list(map(int, input().split())))


address = {}
dist = {}
for i in range(d+1):
    dist[i] = 0


for y in range(h):
    for x in range(w):
        address[graph[y][x]] = [y, x]


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


for i, j in query:
    print(dist[j] - dist[i])

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

d = [None for _ in range(H * W + 1)]
for i in range(H):
    for j in range(W):
        d[A[i][j]] = (i, j)

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

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

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


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



def cost(x, y): 
    return abs(lst[x][0] - lst[y][0]) + abs(lst[x][1] - lst[y][1])

check_lst = [False] * (H * W + 1)
cost_lst = [0] * (H * W + 1)
for i in range(1, D + 1):
    if check_lst[i]:
        continue
    check_lst[i]  = True
    tmp = i
    while tmp + D <= H * W:
        cost_lst[tmp + D] = cost_lst[tmp] + cost(tmp, tmp + D)
        check_lst[tmp + D] = True
        tmp += D


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

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


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



def cost(x, y): 
    return abs(lst[x][0] - lst[y][0]) + abs(lst[x][1] - lst[y][1])

check_lst = [False] * (H * W + 1)
cost_lst = [0] * (H * W + 1)
for i in range(1, H * W + 1):
    if check_lst[i]:
        continue
    check_lst[i]  = True
    tmp = i
    while tmp + D <= H * W:
        cost_lst[tmp + D] = cost_lst[tmp] + cost(tmp, tmp + D)
        check_lst[tmp + D] = True
        tmp += D


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

Solution (Python):
h,w,d=map(int,input().split())
box=[list(map(int,input().split())) for i in range(h)]
adress={}
for i in range(h):
    for j in range(w):
        adress[box[i][j]]=[i,j]
q=int(input())
order=[list(map(int,input().split())) for i in range(q)]
S=[0]*(h*w+1)
for k in range(d+1,h*w+1):
    x,y=adress[k]
    i,j=adress[k-d]
    S[k]=S[k-d]+abs(x-i)+abs(y-j)
for x,y in order:
    print(S[y]-S[x])

Solution (Python):
H, W, D = map(int, input().split())
m = [None] * (H * W + 1)
for i in range(H):
    l = map(int, input().split())
    for j, a in enumerate(l):
        m[a] = (i, j)
Q = int(input())
LR = []
for _ in range(Q):
    l, r = map(int, input().split())
    LR.append((l, r))
 
S = [0] * (H * W + 1)
for k in range(D + 1, H * W + 1):
    x, y = m[k]
    i, j = m[k - D]
    S[k] = S[k - D] + abs(x - i) + abs(y - j)
 
for l, r in LR:
    print(S[r] - S[l])

Solution (Python):
H,W,D = map(int,input().split())
A = list(list(map(int,input().split()))for i in range(H))
B = [[0,0]for i in range(H*W)]
for i in range(H):
    for j in range(W):
        B[A[i][j]-1] = [i,j]
MP = [0]*(H*W)
for i in range(D):
    x,y = B[i]
    for j in range(i+D,H*W,D):
        MP[j] = MP[j-D] + abs(x-B[j][0]) + abs(y-B[j][1])
        x,y = B[j]
for i in range(int(input())):
    l,r = map(int,input().split())
    print(MP[r-1]-MP[l-1])

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

def main():
    H, W, D = map(int, input().split())
    hw = [None for i in range(H*W+1)]

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

    
    
    
    
    modd = [0] * (H*W + 1)
    for start in range(D):
        tmp = start + D
        cost = 0
        if tmp == D:
            tmp = D * 2
        while tmp <= (H*W):
            tmp_cost = abs(hw[tmp][0] - hw[tmp-D][0]) + abs(hw[tmp][1] - hw[tmp-D][1])
            
            
            cost += tmp_cost
            modd[tmp] = cost
            tmp += D
    
    Q = int(input())
    for i in range(Q):
        l, r = map(int, input().split())
        print(modd[r] - modd[l])

if __name__ == "__main__":
    main()

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

a = [[0 for _ in range(w)] for _ in range(h)]
masu = {}
for i in range(h):
    a[i] = list(map(int, input().split()))
    for j in range(w):
        masu[a[i][j]] = (i,j)

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


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

Solution (Python):
H, W, D = map(int, input().split())
m = [None] * (H * W + 1)
for i in range(H):
    l = map(int, input().split())
    for j, a in enumerate(l):
        m[a] = (i, j)
Q = int(input())
LR = []
for _ in range(Q):
    l, r = map(int, input().split())
    LR.append((l, r))

S = [0] * (H * W + 1)
for k in range(D + 1, H * W + 1):
    x, y = m[k]
    i, j = m[k - D]
    S[k] = S[k - D] + abs(x - i) + abs(y - j)

for l, r in LR:
    print(S[r] - S[l])

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7


h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]
q = int(input())
s = [None for _ in range(h*w+1)]
for i in range(h):
    for j in range(w):
        s[a[i][j]] = [i+1,j+1]
D = [[0]*((h*w+1)//d+1) for _ in range(d)]
for i in range(d+1,h*w+1):
    X,Y = s[i]
    Z,W = s[i-d]
    x = abs(X - Z) + abs(Y - W)
    D[i%d][i//d] = x + D[i%d][i//d-1]
for _ in range(q):
    l,r = map(int,input().split())
    x = D[l%d]
    print(x[r//d] - x[l//d])

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

N = H*W
C = [0]*N
pos = [(0,0)]*N
for i in range(H):
    for j in range(W):
        a = A[i][j]-1
        pos[a] = (i,j)
for i in range(D,N):
    C[i] = sum(abs(pos[i][xy]-pos[i-D][xy]) for xy in range(2))
S = [0]*(N+1)
for i in range(D,N+1):
    S[i] = C[i-1] + S[i-D]

for l,r in LR:
    print(S[r] - S[l])

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

memo = [0 for x in range(h*w+1)]
l = 0
for l in range(1, h*w+1-d):
    memo[l+d] = memo[l] + abs(index[l+d][0] - index[l][0]) + abs(index[l+d][1]-index[l][1])

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

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

ACCUM = [0] * (H*W+1)
POS = [None] * (H*W+1)

for i in range(H):
    for j in range(W):
        num=A[i][j]
        POS[num]=(i,j)

for start in range(1,D+1):
    i=start
    cost=0
    while i <= H*W:
        pos0 = POS[i]
        i += D
        if i > H*W: break
        pos1 = POS[i]
        cost += abs(pos0[0]-pos1[0]) + abs(pos0[1]-pos1[1])
        ACCUM[i] = cost

for q in range(Q):
    l,r = LR[q]
    print(ACCUM[r]-ACCUM[l])

Solution (Python):
from collections import defaultdict


def solve(row, col, d):
    x_map = defaultdict()

    for i in range(row):
        a_i = list(map(int, input().split()))
        for j in range(col):
            x_map[a_i[j]] = (i, j)

    q = int(input())

    dp = [0]*(row*col+1)
    for j in range(d+1, row*col+1):
        x_map_y = abs(x_map[j][0] - x_map[j-d][0])
        x_map_x = abs(x_map[j][1] - x_map[j-d][1])
        dp[j] = dp[j-d]+x_map_y+x_map_x



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


if __name__ == '__main__':
    row, col, d = map(int, input().split())
    solve(row, col, d)

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

for i in range(H):
    A = list(map(int, input().split()))
    for j, a in enumerate(A):
        px[a] = i
        py[a] = j

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

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

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

H, W, D = map(int, input().split())
L = [[int(v) - 1 for v in input().split()] for _ in range(H)]
Q = int(input())
QL = [[int(v) - 1 for v in input().split()] for _ in range(Q)]

m = [None] * (H * W)
for i in range(H):
    for j in range(W):
        m[L[i][j]] = (i, j)

dp = [None] * (H * W)
for i in range(D):
    dp[i] = 0
    for j in range(i + D, H * W, D):
        x, y = m[j - D]
        nx, ny = m[j]
        
        dp[j] = dp[j - D] + abs(x - nx) + abs(y - ny)

for qx, qy in QL:
    print(dp[qy] - dp[qx])

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

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

numbers_sum = [0] * (H * W + 1)
for n in range(D + 1, H * W + 1):
	f, t = numbers[n], numbers[n - D]
	cost = abs(f[0] - t[0]) + abs(f[1] - t[1])
	numbers_sum[n] = numbers_sum[n - D] + cost

for l, r in LR:
	print(numbers_sum[r] - numbers_sum[l])

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

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

Solution (Python):
import sys
sys.setrecursionlimit(100001)
def input():
    return sys.stdin.readline()[:-1]

from collections import defaultdict
H, W, D = map(int, input().split())
dic = defaultdict()
for i in range(H):
    a = list(map(int, input().split()))
    for j in range(W):
        dic[a[j]] = [i, j]
dist = [0 for i in range(H*W+1)]
for i in range(1, D+1):
    for j in range(i, H*W-D+1, D):
        dist[j+D] = abs(dic[j][0] - dic[j+D][0]) + abs(dic[j][1] - dic[j+D][1])
for i in range(1, D+1):
    for j in range(i+D, H*W+1, D):
        dist[j] += dist[j-D]
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(dist[r] - dist[l])

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

h,w,d = map(int,input().split())
ahw = [0]*(h*w)
dp = [0]*(h*w)
for i in range(h):
  temp = [int(i)-1 for i in input().split()]
  for j in range(w):
    ahw[temp[j]] = (i,j)
for i in range(d):
  dp[i] = 0
for i in range(d,h*w):
  dp[i] = dp[i-d] + abs(ahw[i][0]-ahw[i-d][0]) + abs(ahw[i][1]-ahw[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())
integer=[0]*(1+h*w)
for i in range(h):
    a_list=list(map(int,input().split()))
    for j in range(w):
        integer[a_list[j]]=((i+1,j+1))
dp=[0]*(1+h*w)
for i in range(h*w-d+1,h*w+1):
    dp[i]=0
    pre=i
    now=i-d
    while now>0:
        dp[now]=dp[pre]+abs(integer[now][0]-integer[pre][0])+abs(integer[now][1]-integer[pre][1])
        pre=now
        now=now-d
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(dp[l]-dp[r])

Solution (Python):
H,W,D=map(int,input().split())
A=[list(map(lambda x:int(x)-1,input().split())) for _ in [0]*H]
Q=int(input())
LR=[list(map(lambda x:int(x)-1,input().split())) for _ in [0]*Q]
dic=[None]*(H*W)
dic2=[None]*(H*W)

for i in range(H):
    for j in range(W):
        dic[A[i][j]]=(i,j)

for i in range(H*W):
    if i<D:
        dic2[i]=0
    else:
        dic2[i]=dic2[i-D]+abs(dic[i][0]-dic[i-D][0])+abs(dic[i][1]-dic[i-D][1])

for i in range(Q):
    print(dic2[LR[i][1]]-dic2[LR[i][0]])

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

grid = [0]
manta = lambda x,y:abs(x[0]-y[0])+abs(x[1]-y[1])
for i in range(1, H*W+1):
    if (i-1) // D == 0:
        grid.append(0)
    else:
        grid.append(manta(A[i], A[i-D]) + grid[i-D])
for l,r in exam:
    print(grid[r]-grid[l])

Solution (Python):
H,W,D = map(int, input().split())
grid_dict = {}
for i in range(H):
    for j,s in enumerate(input().split()):
        grid_dict[int(s)] = [i,j]

Q = int(input())
exam = []
for i in range(Q):
    exam.append(list(map(int, input().split())))

man = lambda x,y: abs(x[0]-y[0])+abs(x[1]-y[1])

power = [[0] for i in range(D)]
power[0].append(0)
for i in range(1,H*W+1):
    if i + D not in grid_dict:
        break
    power[i%D].append(power[i%D][-1] + man(grid_dict[i], grid_dict[i+D]))


for l,r in exam:
    if r == l:
        print(0)
        continue
    print(power[r%D][r//D]-power[r%D][l//D])

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

masu=[]

for j in range(H):
  L=list(map(int,input().split()))
  for i in range(W):
    masu.append(tuple((L[i],j+1,i+1)))
masu=sorted(masu,key=lambda x:x[0])


dp=[0]*(H*W)


for i in range(D,H*W):
  dp[i]=dp[i-D]+abs(masu[i][1]-masu[i-D][1])+abs(masu[i][2]-masu[i-D][2])


Q=int(input())

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