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):
h,w,d=map(int,input().split())
dict={}

for i in range(1,h+1):
  lst=list(map(int,input().split()))
  for j in range(w):
    dict.setdefault(lst[j],(i,j+1))

cost=[0]*(h*w)

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


ans=0

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

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

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W, D = LI()
    A = [LI_() for _ in range(H)]
    Q = I()

    c = [[] for _ in range((H * W))]
    for i, j in itertools.product(range(H), range(W)):
        c[A[i][j]] = [i, j]

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

    for _ in range(Q):
        L, R = LI_()
        ans = c_cum[R] - c_cum[L]
        print(ans)

if __name__ == '__main__':
    resolve()

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

from collections import defaultdict
dic = {}
for h in range(H):
    for w in range(W):
        a = As[h][w]
        dic[a] = (h, w)

cost_dic = defaultdict(int)
for i in range(d+1, H*W+1):
    oh, ow = dic[i-d]
    h, w = dic[i]
    cost_dic[i] = cost_dic[i-d]+abs(h-oh)+abs(w-ow)

for _ in range(Q):
    l, r = mapint()
    print(cost_dic[r]-cost_dic[l])

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

from collections import defaultdict
from itertools import accumulate
from bisect import bisect_left
dic = defaultdict(list)
for h in range(H):
    for w in range(W):
        a = As[h][w]
        dic[a%d].append((a, h, w))

cost_dic = {}
for m in dic.keys():
    dic[m].sort()
    sa, sh, sw = dic[m][0]
    cost_dic[m] = [0]
    for a, h, w in dic[m][1:]:
        cost = abs(h-sh)+abs(w-sw)
        cost_dic[m].append(cost)
        sa, sh, sw = a, h, w
    cost_dic[m] = list(accumulate(cost_dic[m]))

for _ in range(Q):
    l, r = mapint()
    sidx = bisect_left(dic[l%d], (l, 0, 0))
    eidx = bisect_left(dic[l%d], (r, 0, 0))
    print(cost_dic[l%d][eidx]-cost_dic[l%d][sidx])

Solution (Python):
h,w,d = map(int,input().split())
lst = [0]*(h*w+1)
for i in range(h):
    a = list(map(int,input().split()))
    for j in range(w):
        lst[a[j]] = (i,j)
cost = [0]*(h*w+1)
for t in range(1,d+1):
    now = t
    while now <= h*w-d:
        nxt = now+d
        x0,y0 = lst[now]
        x1,y1 = lst[nxt]
        cost[nxt] = cost[now]+abs(x0-x1)+abs(y0-y1)
        now += d
q = int(input())
for i in range(q):
    l,r = map(int,input().split())
    print(cost[r]-cost[l])

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

max_value = H*W

position = [0]*(max_value+1)

root_cost = [0]*(max_value+1)

for y in range(H):
    A = list(map(int,input().split()))
    for x in range(W):
        position[A[x]] = (x+1,y+1)

for i in range(1,max_value+1):
    if 0 < i-D:
        x1,y1 = position[i-D]
        x2,y2 = position[i]
        root_cost[i] = root_cost[i-D]+(abs(x2-x1)+abs(y2-y1))

Q=int(input())

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

Solution (Python):
import sys
input=sys.stdin.readline
H,W,D=map(int,input().split())
cost=[[0 for _ in range((H*W)//D+1)] for i in range(D)]
L=[0]*(H*W)
for i in range(H):
  L1=list(map(int,input().split()))
  for j in range(W):
    L[L1[j]-1]=[i,j]
    if L1[j]%D!=0:
      cost[L1[j]%D][L1[j]//D]=[i,j,0]
    else:
      cost[L1[j]%D][(L1[j]//D)-1]=[i,j,0]
for i in range(D):
  for j in range(1,len(cost[i])):
    if cost[i][j]!=0:
      cost[i][j][2]=cost[i][j-1][2]+abs(cost[i][j][0]-cost[i][j-1][0])+abs(cost[i][j][1]-cost[i][j-1][1])
Q=int(input())
for i in range(Q):
  A,B=map(int,input().split())
  c=A%D
  a=A//D
  b=B//D
  if c==0:
    a,b=a-1,b-1
  print(cost[c][b][2]-cost[c][a][2])

Solution (Python):
import sys
readline=sys.stdin.readline
read=sys.stdin.read
 
h,w,d=map(int,readline().split())
a=[list(map(int,readline().split())) for _ in range(h)]
q,*lr=map(int,read().split())

ca=dict()
for i,l in enumerate(a):
  for j,e in enumerate(l):
    ca[e]=(i+1,j+1)
mp=[[0]*((h*w)//d+1) for _ in range(d)]
for i,mpl in enumerate(mp):
  for j,_ in enumerate(mpl[:-1]):
    if 0<i+d*j<=h*w-d:
      mpl[j+1]=mpl[j]+abs(ca[i+d*j][0]-ca[i+d*(j+1)][0])\
                +abs(ca[i+d*j][1]-ca[i+d*(j+1)][1])
for l,r in zip(*[iter(lr)]*2):
  print(mp[l%d][r//d]-mp[l%d][l//d])

Solution (Python):
import sys
import math
import collections
import bisect
import itertools



sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))




def main():
    h, w, d = ns()
    pos = dict()
    for i in range(h):
        a = na()
        for j, ai in enumerate(a):
            pos[ai - 1] = (i, j)

    cum = [[0] for _ in range(d)]

    for i in range(d):
        x, y = pos[i]
        num = i + d
        while num < h * w:
            xi, yi = pos[num]
            tmp = abs(xi - x) + abs(yi - y)
            cum[i].append(cum[i][-1] + tmp)
            x, y = xi, yi
            num += d

    q = ni()
    for _ in range(q):
        l, r = ns()
        l, r = l - 1, r - 1
        tmp = cum[l % d][r // d] - cum[l % d][l // d]
        print(tmp)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
import collections
import bisect
import itertools



sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))




def main():
    h, w, d = ns()
    pos = dict()
    for i in range(h):
        a = na()
        for j, ai in enumerate(a):
            pos[ai - 1] = (i, j)

    cum = [[0] for _ in range(d)]

    for i in range(d):
        x, y = pos[i]
        num = i
        while num + d < h * w:
            num += d
            xi, yi = pos[num]
            tmp = abs(xi - x) + abs(yi - y)
            cum[i].append(cum[i][-1] + tmp)
            x, y = xi, yi

    q = ni()
    for _ in range(q):
        l, r = ns()
        l, r = l - 1, r - 1
        tmp = cum[l % d][r // d] - cum[l % d][l // d]
        print(tmp)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
import collections
import bisect
import itertools



sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline().rstrip())
ns = lambda: map(int, sys.stdin.readline().rstrip().split())
na = lambda: list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().rstrip().split()))




def main():
    h, w, d = ns()
    pos = dict()
    for i in range(h):
        a = na()
        for j, ai in enumerate(a):
            pos[ai] = (i, j)

    cum = [[0] for _ in range(d)]

    for i in range(d):
        x, y = pos[i + 1]
        num = i + 1
        while num + d <= h * w:
            num += d
            xi, yi = pos[num]
            tmp = abs(xi - x) + abs(yi - y)
            cum[i].append(cum[i][-1] + tmp)
            x = xi
            y = yi

    q = ni()
    for _ in range(q):
        l, r = ns()
        l -= 1
        r -= 1
        tmp = cum[l % d][r // d] - cum[l % d][l // d]
        print(tmp)


if __name__ == '__main__':
    main()

Solution (Python):
import sys,math,collections,itertools
input = sys.stdin.readline

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


dict_map = {}
for ih in range(H):
    for iw in range(W):
        dict_map[A[ih][iw]]=(ih,iw)

memo = [-1]*(H*W+1)
for i in range(1,D+1):
    useMP = 0
    direct = range(i,H*W+1,D)
    memo[i]=0
    for p in range(len(direct)-1):
        x0,y0 = dict_map[direct[p]]
        x1,y1 = dict_map[direct[p+1]]
        dist = abs(x0-x1)+abs(y0-y1)
        useMP += dist
        memo[direct[p+1]]=useMP

for q in range(Q):
    L,R=LR[q]
    print(memo[R]-memo[L])

Solution (Python):
h,w,d = map(int, input().split())
al = []
num_to_xy = [(-1,-1)]*(h*w+1)
for hi in range(h):
    row = list(map(int, input().split()))
    for wi,v in enumerate(row):
        num_to_xy[v] = (hi+1, wi+1)

dist_l = [ [] ]*(d+1)
for start in range(1,d+1):
    dists = [0]
    c_dist = 0
    for i in range(start, h*w-d+1, d):
        x1,y1 = num_to_xy[i]
        x2,y2 = num_to_xy[i+d]
        dist = abs(x2-x1) + abs(y2-y1)
        c_dist += dist
        dists.append(c_dist)
    dist_l[start] = dists


ansl = []
q = int(input())
for _ in range(q):
    l,r = map(int, input().split())
    start = l%d
    if start == 0: start = d
    posl, posr = (l-start)//d, (r-start)//d
    ans = dist_l[start][posr] - dist_l[start][posl]
    ansl.append(ans)

for a in ansl: print(a)

Solution (Python):
import sys

H, W, D = map(int, sys.stdin.readline().split())
num = {}
for j in range(H):
    tmp = map(int, sys.stdin.readline().split())
    for i, n in enumerate(tmp):
        num[n] = (i, j)



S = [0 for _ in range(H*W+D)]
for i in range(D+1, H*W+1):
    x, y = num[i]
    a, b = num[i-D]
    S[i] = S[i-D] + abs(x - a) + abs(y - b)

Q = int(sys.stdin.readline())
for _ in range(Q):
    L, R = map(int, sys.stdin.readline().split())
    r = L % D
    print(S[R] - S[L])

Solution (Python):
import sys

H, W, D = map(int, sys.stdin.readline().split())
num = {}
for j in range(H):
    tmp = map(int, sys.stdin.readline().split())
    for i, n in enumerate(tmp):
        num[n] = (i, j)



S = [0 for _ in range(H*W+D)]
for i in range(D+1, H*W+1):
    x, y = num[i]
    a, b = num[i-D]
    S[i] = S[i-D] + abs(x - a) + abs(y - b)

Q = int(sys.stdin.readline())
for _ in range(Q):
    L, R = map(int, sys.stdin.readline().split())
    r = L % D
    print(S[R] - S[L])

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

xy = {}
for x, ai in enumerate(a):
    for y, aij in enumerate(ai):
        xy[aij] = (x, y)

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

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

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

xy = {}
for x, ai in enumerate(a):
    for y, aij in enumerate(ai):
        xy[aij] = (x, y)

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

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

Solution (Python):
import itertools
I = [int(_) for _ in open(0).read().split()]
H, W, D = I[:3]
A = I[3:3 + H * W]
Q = I[3 + H * W]
LR = I[4 + H * W:]

a_i = [0] * (H * W + 1)
for i, a in enumerate(A):
    a_i[a] = i


def calc(a1):
    a2 = a1 + D
    hw1 = a_i[a1]
    h1, w1 = divmod(hw1, W)
    hw2 = a_i[a2]
    h2, w2 = divmod(hw2, W)
    return abs(h2 - h1) + abs(w2 - w1)


score = [0] + [calc(i) for i in range(1, H * W + 1 - D)]
cum = [[0] + list(itertools.accumulate(score[i::D])) for i in range(D)]
ans = []
for l, r in zip(LR[::2], LR[1::2]):
    ans += [cum[r % D][r // D] - cum[l % D][l // D]]
print(*ans, sep='\n')

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

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

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

    ans = [0] * Q
    for i, (l, r) in enumerate(zip(*[iter(LR)] * 2)):
        ans[i] = csum[r] - csum[l]

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    vec = [0] * (H * W + 1)
    for i in range(H):
        for j in range(W):
            vec[A[i][j]] = (i + 1, j + 1)
    vec[0] = vec[D]

    csum = [0] * D
    for i in range(D):
        N = (H * W - i) // D + 1
        csum[i] = [0] * N
        for j in range(N - 1):
            csum[i][j + 1] = (
                csum[i][j]
                + abs(vec[i + (j + 1) * D][0] - vec[i + j * D][0])
                + abs(vec[i + (j + 1) * D][1] - vec[i + j * D][1])
            )

    ans = [0] * Q
    for i, (l, r) in enumerate(zip(*[iter(LR)] * 2)):
        n, m = divmod(l, D)
        ans[i] = csum[m][(r - l) // D + n] - csum[m][n]

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


if __name__ == '__main__':
    main()

Solution (Python):


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def manhattan(p0, p1):
    return abs(p0[0]-p1[0])+abs(p0[1]-p1[1])


def solve():
    """
    """
    H, W, D = read_ints()
    arr = [None for _ in range(H*W)]
    for i in range(H):
        for j, a in enumerate(read_ints()):
            arr[a-1] = (i, j)
    prefix = [0]*(H*W)
    for i in range(D):
        for j in range(i+D, H*W, D):
            prefix[j] = prefix[j-D]+manhattan(arr[j], arr[j-D])
    Q = read_int()
    for _ in range(Q):
        l, r = read_ints()
        print(prefix[r-1]-prefix[l-1])




if __name__ == '__main__':
    solve()

Solution (Python):
def dist(d1, d2):
    return abs(d1[0] - d2[0]) + abs(d1[1] - d2[1])


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

table = {}

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

cum = [0] * (h * w + 1)
for i in range(h * w + 1):
    if i > d:
        cum[i] = cum[i - d] + dist(table[i], table[i - d])


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

Solution (Python):
def main():
    h, w, d = map(int, input().split())
    ans = [[0] for _ in range(d)]
    s = [0] * d
    ans[0].append(0)
    dict = {}
    for i in range(h):
        for j, a in enumerate(list(map(int, input().split()))):
            dict[a] = (i, j)
    for i in range(1, h * w + 1 - d):
        m = i % d
        s[m] += abs(dict[i][0] - dict[i + d][0]) + abs(dict[i][1] - dict[i + d][1])
        ans[m].append(s[m])
    q = int(input())
    for _ in range(q):
        l, r = map(int, input().split())
        m = l % d
        print(ans[m][r // d] - ans[m][l // d])

if __name__ == '__main__':
    main()

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

    a = [None] * (h * w + 1)
    for i in range(1, h + 1):
        l = map(int, input().split())
        for j, k in enumerate(l, 1):
            a[k] = (i, j)

    c = [0] * (h * w + 1)
    for i in range(d + 1, h * w + 1):
        xb, yb = a[i-d]
        xn, yn = a[i]
        c[i] = c[i - d] + abs(xn - xb) + abs(yn - yb)

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

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


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(1000000)
    h, w, d = map(int, input().split())
    p = []
    for i in range(1, h + 1):
        l = map(int, input().split())
        for j, k in enumerate(l, 1):
            p.append((k, (i, j)))
    p.sort(key=lambda x: x[0])

    q = int(input())

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

    def Q(i, c, x, y):
        if i + d > w * h:
            return
        _, (nx, ny) = p[i + d - 1]
        nc = c + abs(nx - x) + abs(ny - y)
        dist[i + d] = nc
        Q(i + d, nc, nx, ny)

    for i in range(d):
        n, (x, y) = p[i]
        Q(n, 0, x, y)

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

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


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from itertools import accumulate
    h, w, d = map(int, input().split())

    a = [0] * (h * w + 1)
    b = [0] * (h * w + 1)
    for i in range(1, h + 1):
        l = map(int, input().split())
        for j, k in enumerate(l, 1):
            a[k] = i
            b[k] = j

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

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

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


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    H, W, D = [int(x) for x in input().strip().split()]
    M = [0] * H
    C = {}
    revM = {}
    for h in range(H):
        M[h] = [int(x) for x in input().strip().split()]
        for i, w in enumerate(M[h]):
            revM[w] = (h, i)
    Q = int(input())
    HW = H * W
    ans = [0] * (HW + 1)
    for i in range(1, D+1):
        cur = i
        while cur + D <= HW:
            ans[cur+D] += ans[cur] + abs(revM[cur][0] - revM[cur+D][0]) + abs(revM[cur][1] - revM[cur+D][1])
            cur += D

    for q in range(Q):
        l, r = [int(x) for x in input().strip().split()]
        print(ans[r]-ans[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)]
b = [0]*(h*w+1)
for i in range(h):
    for j in range(w):
        b[a[i][j]] = (i,j)

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

for i in range(q):
    x,y = lr[i][0],lr[i][1]
    print(ans[y]-ans[x])

Solution (Python):
import collections
h,w,d = map(int, raw_input().split())
mat = [map(int, raw_input().split()) for i in range(h)]
coord,cost = {mat[i][j]:(i,j) for i in range(len(mat)) for j in range(len(mat[0]))}, collections.Counter()
def f(uu,vv): 
	return abs(uu[0] -vv[0]) + abs(uu[1] -vv[1]) 
for u in range(1, h * w + 1):
	if u - d >= 1: cost[u] = f(coord[u], coord[u - d]) + cost[u - d]
for qi in  range(int(raw_input())):
	u,v = map(int, raw_input().split())
	print cost[v] - cost[u]

Solution (Python):
H,w,d = map(int, raw_input().split())
mat = [map(int, raw_input().split()) for i in range(H)]

h = {}
cost = {}
for i in range(len(mat)):
	for j in range(len(mat[0])):
		h[mat[i][j]] = (i,j)

import collections
cost = collections.Counter()
def f(uu,vv): return abs(uu[0] -vv[0]) + abs(uu[1] -vv[1]) 
for u in range(1,H*w + 1):
	if u - d >= 1: cost[u] = f(h[u], h[u - d]) + cost[u - d]


def g(u,v, cost,d): return cost[v] - cost[u]

for qi in  range(int(raw_input())):
	u,v = map(int, raw_input().split())
	print g(u,v,cost, d)

Solution (Python):
H,w,d = map(int, raw_input().split())
mat = [map(int, raw_input().split()) for i in range(H)]

h = {}
cost = {}
for i in range(len(mat)):
	for j in range(len(mat[0])):
		h[mat[i][j]] = (i,j)

cost = {}
def f(uu,vv): return abs(uu[0] -vv[0]) + abs(uu[1] -vv[1]) 
for u in range(1,H*w + 1):
	if u - d >= 1:
		cost[u] = f(h[u], h[u - d]) + cost[u - d]
	else:
		cost[u] = 0 

def g(u,v, cost,d):
	p = u
	return cost[v] - (cost[p] if p in cost else 0) 

for qi in  range(int(raw_input())):
	u,v = map(int, raw_input().split())
	print g(u,v,cost, d)

Solution (Python):

import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

def main():
    H, W, D = map(int, input().split())
    A = [None] * (H*W)
    for i in range(H):
        s = list(map(int, input().split()))
        for j in range(W):
            A[s[j]-1] = (i,j)

    
    costs = [0]*(H*W)
    for i in range(D):
        j = H*W-1-i
        while j-D >= 0:
            costs[j-D] = costs[j] + abs(A[j][0]-A[j-D][0]) + abs(A[j][1]-A[j-D][1])
            j -= D
    
    Q = int(input())
    for i in range(Q):
        L, R = map(lambda x: int(x)-1, input().split())
        print(costs[L]-costs[R])

if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict

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

d = defaultdict(list)
for i in range(H):
    for j in range(W):
        d[A[i][j]].append([i, j])


p = []
for s in range(1, D + 1):
    c = 0
    q = [0]
    for i in range(s + D, H * W + 1, D):
        i0, j0 = d[i - D][0]
        i1, j1 = d[i][0]
        c += abs(i0 - i1) + abs(j0 - j1)
        q.append(c)
    p.append(q)


for l, r in LR:
    i = l % D - 1
    s = (l - 1) // D
    e = (r - 1) // D
    print(p[i][e] - p[i][s])

Solution (Python):
from collections import defaultdict

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







d = defaultdict(list)
for i in range(H):
    for j in range(W):
        d[A[i][j]].append([i, j])


p = []
for s in range(1, D + 1):
    c = 0
    q = [0]
    for i in range(s + D, H * W + 1, D):
        i0, j0 = d[i - D][0]
        i1, j1 = d[i][0]
        c += abs(i0 - i1) + abs(j0 - j1)
        q.append(c)

    p.append(q)


for l, r in LR:
    i = l % D - 1
    s = (l - 1) // D
    e = (r - 1) // D
    print(p[i][e] - p[i][s])

Solution (Python):
import sys
readline = sys.stdin.readline
h, w, d = map(int, readline().split())
A = [list(map(int, readline().split())) for _ in range(h)]
q = int(readline())
LR = [tuple(map(lambda x:int(x)-1, readline().split())) for _ in range(q)]

D = dict()
for hi in range(h):
    for wi in range(w):
        D[A[hi][wi]-1] = [hi,wi]

DP = [0]*(h*w)
for i in range(d, h*w):
    px, py = D[i-d]
    x, y = D[i]
    DP[i] = DP[i-d] + abs(x-px) + abs(y-py)

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

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

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

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

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

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

mp=[[0] for i in range(d)]

for i in range(d):
    tmp=i
    while tmp+d<h*w:
        x=abs(grid[tmp+d][0]-grid[tmp][0])+abs(grid[tmp+d][1]-grid[tmp][1])
        mp[i].append(x+mp[i][-1])
        tmp+=d
q=int(input())
for _ in range(q):
    l,r=map(int,input().split())
    l,r=l-1,r-1
    tmp=mp[r%d][(r-(r%d))//d]-mp[l%d][(l-(l%d))//d]
    print(tmp)

Solution (Python):
import sys
from itertools import accumulate

input = sys.stdin.readline


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

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

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

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

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


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

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from itertools import accumulate

input = sys.stdin.readline


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

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

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

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

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


def main():
    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)]

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from itertools import accumulate

input = sys.stdin.readline


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

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

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

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

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


def main():
    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)]

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from itertools import accumulate

input = sys.stdin.readline


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

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

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

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

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


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

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


if __name__ == "__main__":
    main()

Solution (Python):
import sys
from itertools import accumulate

input = sys.stdin.readline


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

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

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

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

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


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

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


if __name__ == "__main__":
    main()