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



Sample input:
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8


Sample output:
5

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(H: int, W: int, D: int, A: "List[List[int]]", Q: int, L: "List[int]", R: "List[int]"):
    N = H*W

    ## ある数字の座標をO(1)で取得するため
    matrix = [()]*(N+1)
    for h in range(H):
        for w in range(W):
            matrix[A[h][w]] = (h,w)
    
    def get_distance(start: int, end: int) -> int:
        start_x = matrix[start][0]
        start_y = matrix[start][1]
        end_x = matrix[end][0]
        end_y = matrix[end][1]
        return abs(start_x-end_x)+abs(start_y-end_y)

    distance = []

    for start in range(1,D+1):
        end = start
        ## 初期化
        distance_matrix = {}
        while end <= N:
            distance_matrix[end] = 0
            end += D

        end = start
        prev_end = end

        while end <= N:
            distance_matrix[end] = distance_matrix[prev_end]+ get_distance(prev_end,end)
            prev_end = end
            end += D
        
        distance.append(distance_matrix)
    
    for i in range(Q):
        s = L[i]%D
        if s == 0:
            s = D
        distance_matrix = distance[s-1]
        d = distance_matrix[R[i]]-distance_matrix[L[i]]
        print(d)

    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))  # type: int
    W = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(W)] for _ in range(H)]  # type: "List[List[int]]"
    Q = int(next(tokens))  # type: int
    L = [int()] * (Q)  # type: "List[int]"
    R = [int()] * (Q)  # type: "List[int]"
    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()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H, W, D = MAP()
A = [LIST() for _ in range(H)]

Q = INT()
LR = [LIST() for _ in range(Q)]

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

for i in range(H):
	for j in range(W):
		dic[A[i][j]%D].append([A[i][j], i, j])

for lis in dic:
	lis.sort(key=lambda x:x[0])

for lis in dic:
	lis[0][0] = 0
	for i in range(len(lis)):
		if i == len(lis)-1:
			break
		point = (lis[i][1], lis[i][2])
		dist_point = (lis[i+1][1], lis[i+1][2])
		lis[i+1][0] = lis[i][0] + abs(point[0]-dist_point[0]) + abs(point[1]-dist_point[1])

for L, R in LR:
	print(dic[R%D][ceil(R/D)-1][0]-dic[R%D][ceil(L/D)-1][0])

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
field=[[]]*(h*w)
for i in range(h):
	x=list(map(int,input().split()))
	for j in range(w):
		field[x[j]-1]=[i,j]
dis=[10**20]*(h*w)
for i in range(d):
	dis[i]=0
for i in range((h*w)):
	if i>=d:
		dis[i]=dis[i-d]+abs(field[i][0]-field[i-d][0])\
		+abs(field[i][1]-field[i-d][1])
q=int(input())
for i in range(q):
	l,r=map(int,input().split())
	print(dis[r-1]-dis[l-1])

Submission status: Accepted

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

al_l = []
for _ in range(h):
    al = list(map(int,input().split()))
    al_l.append(al)

from collections import defaultdict
dic = {}
for i in range(h):
    for j in range(w):
        dic[al_l[i][j]] = (i,j)

path = {}
for i in range(1,d+1):
    tmp = 0
    while True:
        path[i] = tmp
        i += d
        if i > h*w:
            break
        x1, y1 = dic[i]
        x2, y2 = dic[i-d]
        tmp += abs(x1-x2) + abs(y2-y1)

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

Submission status: Accepted

Solution code:
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)]

number_list = [[0] * 2 for _ in range(H*W+1)]
for h in range(H):
    for w in range(W):
        number_list[A[h][w]] = [h, w]

d = [0] * (H*W+1)
for idx in range(H*W+1):
    pre_idx = idx - D
    if pre_idx <= 0:
        continue
    diff = abs(number_list[idx][0] - number_list[pre_idx][0])
    diff += abs(number_list[idx][1] - number_list[pre_idx][1])
    d[idx] = d[pre_idx] + diff

for l, r in LR:
    cnt = 0
    print(d[r] - d[l])

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
field=[[]]*(h*w)
for i in range(h):
	x=list(map(int,input().split()))
	for j in range(w):
		field[x[j]-1]=[i,j]
dis=[10**20]*(h*w)
for i in range(d):
	dis[i]=0
for i in range((h*w)):
	if i>=d:
		dis[i]=dis[i-d]+abs(field[i][0]-field[i-d][0])\
		+abs(field[i][1]-field[i-d][1])
q=int(input())
for i in range(q):
	l,r=map(int,input().split())
	print(dis[r-1]-dis[l-1])

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
l=[]
for i in range(h):
    l.append(list(map(int,input().split())))
px=[0]*(h*w)
py=[0]*(h*w)
ans=[0]*(h*w)
for i in range(h):
    for j in range(w):
        px[l[i][j]-1]=j
        py[l[i][j]-1]=i
for i in range(d,h*w):
    ans[i]=ans[i-d]+abs(px[i]-px[i-d])+abs(py[i]-py[i-d])
q=int(input())
for i in range(q):
    a,b=map(int,input().split())
    print(ans[b-1]-ans[a-1])

Submission status: Accepted

Solution code:
H,W,D=map(int,input().split())
import collections
import bisect
table=collections.defaultdict(list)
table2=collections.defaultdict(list)
dp=collections.defaultdict(list)
field=[list(map(int,input().split())) for i in range(H)]
for i in range(H):
  for j in range(W):
    table[field[i][j]%D].append((field[i][j],i,j))
    table2[field[i][j]%D].append(field[i][j])
for x in table:
  table[x].sort(key=lambda x:x[0])
  dp[x]=[0]*len(table[x])
  for i in range(1,len(table[x])):
    dp[x][i]=dp[x][i-1]+abs(table[x][i][1]-table[x][i-1][1])+abs(table[x][i][2]-table[x][i-1][2])
  table2[x].sort()
Q=int(input())
LR=[list(map(int,input().split())) for i in range(Q)]
for i in range(Q):
  ans=0
  x,y = LR[i]
  
  id = bisect.bisect_left(table2[x%D],x)
  id2=bisect.bisect_left(table2[x%D],y)
  print(dp[x%D][id2]-dp[x%D][id])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    h,w,d=map(int,input().split())
    grid=[]
    cnt=0
    for i in range(h):
        for j,a in enumerate(map(int,input().split())):
            a-=1
            grid.append((a,(i,j)))
    grid.sort()

    n=h*w
    A=list(map(lambda x:x[1],grid))
    C=[0]*n
    for r in range(d):
        for x in range(r,n-d,d):
            C[x+d]=C[x]+abs(A[x+d][0]-A[x][0])+abs(A[x+d][1]-A[x][1])

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

Submission status: Accepted

Solution code:
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)]

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

cost = [[0 for _ in range((H * W) // D + 1)] for _ in range(D)]
for i in range(H * W):
  d, m = divmod(i, D)
  if d > 0:
    cost[m][d] = cost[m][d - 1] + abs(li[i][0] - li[i - D][0]) + abs(li[i][1] - li[i - D][1]) 

# print(cost)

for l, r in LR:
  print(cost[(l - 1) % D][(r - 1) // D] - cost[(l - 1) % D][(l - 1) // D])

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
X = [(0, 0) for _ in range(H*W)]
Y = [0] * (H*W)
for i in range(H):
    A = [int(a) - 1 for a in input().split()]
    for j in range(W):
        X[A[j]] = (i, j)
for i in range(H*W - D):
    Y[i+D] = Y[i] + abs(X[i+D][0] - X[i][0]) + abs(X[i+D][1] - X[i][1])
for _ in range(int(input())):
    l, r = map(int, input().split())
    print(Y[r-1] - Y[l-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
h, w, d = map(int, input().split())
x = [None] * h * w
y = [[0] for _ in range(d)]
for i in range(h):
    r = [int(x) for x in input().split()]
    for j in range(w):
        x[r[j] - 1] = (i, j)
for i in range(d):
    for j in range(i + d, h * w, d):
        y[i].append(abs(x[j][0] - x[j - d][0]) + abs(x[j][1] - x[j - d][1]))
        y[i][-1] += y[i][-2]
for _ in range(int(input())):
    l, r = [int(x) - 1 for x in input().split()]
    m = l % d
    print(y[m][r // d] - y[m][l // d])

Submission status: Accepted

Solution code:
#practical skill test
h,w,d=map(int,input().split())
lists=[0 for j in range(h)]
for j in range(h):
    lis=list(map(int,input().split()))
    lists[j]=lis
uselist=[0 for i in range(h*w)]
for i in range(h):
    for j in range(w):
        uselist[lists[i][j]-1]=(i+1,j+1)

distance=[[0]for i in range(d)]
for i in range(1,d+1):
    start=i
    nums=0
    #i=1,2,....,d
    while start<=h*w-d:
        a=abs(uselist[start+d-1][0]-uselist[start-1][0])+abs(uselist[start+d-1][1]-uselist[start-1][1])
        nums=nums+a
        distance[i-1].append(nums)
        start+=d

q=int(input())
for k in range(q):
    s,g=map(int,input().split())
    if s%d!=0:
      mod=s%d-1
    elif s%d==0:
      mod=d-1
    print(distance[mod][(g-1-mod)//d]-distance[mod][(s-1-mod)//d])

Submission status: Accepted

Solution code:
h, w, d = map(int, input().split())
cell = {}
for i in range(h):
  row = list(map(int, input().split()))
  for j, a in enumerate(row):
    cell[a] = (i, j)

max_point = h * w
req_mp = [0 for i in range(max_point)]
for i in range(max_point):
  if i < d:
    req_mp[i] = 0
  else:
    temp = req_mp[i-d]
    temp += abs(cell[i-d+1][0] - cell[i+1][0])
    temp += abs(cell[i-d+1][1] - cell[i+1][1])
    req_mp[i] = temp

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

Submission status: Accepted

Solution code:
# TLE
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1

def main():
    h, w, d = map(int, input().split())
    atoij = [[] for _ in range(h * w)]
    for i in range(h):
        for j, a in enumerate(map(int, input().split())):
            a -= 1
            atoij[a] = [i, j]
    # print(atoij)
    q = int(input())
    ans=[0]*q
    mx = [0] * d
    mn = [100000] * d
    qq = [[] for _ in range(d)]
    for qi in range(q):
        l, r = map(int1, input().split())
        md = l % d
        if l < mn[md]: mn[md] = l
        if r > mx[md]: mx[md] = r
        qq[md].append([qi, l, r])
    for md in range(d):
        if not qq[md]: continue
        a = mn[md]
        ed = mx[md]
        s = 0
        dist = {}
        i0, j0 = atoij[a]
        while a <= ed:
            i1, j1 = atoij[a]
            s += abs(i0 - i1) + abs(j0 - j1)
            dist[a] = s
            i0, j0 = i1, j1
            a += d
        for qi, l, r in qq[md]:
            ans[qi]=dist[r]-dist[l]
    for x in ans:
        print(x)

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def main():
    H, W, D = map(int, input().split())
    d = [0]*(H*W)
    for h in range(H):
        a = list(map(int, input().split()))
        for i, x in enumerate(a):
            d[x-1] = h*W + i

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


def main():
    H, W, D = map(int, input().split())
    A = []
    d = [0]*(H*W)
    for h in range(H):
        a = list(map(int, input().split()))
        A.append(a)
        for i, x in enumerate(a):
            d[x-1] = h*W + i
    mp = [0]*(H*W)
    for i in range(H*W):
        if i >= D:
            mp[i] = mp[i-D] + abs(d[i]//W - d[i-D]//W) + abs(d[i]%W - d[i-D]%W)
    Q = int(input())
    for q in range(Q):
        ans = 0
        l, r = map(int, input().split())
        print(mp[r-1] - mp[l-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

L=[[0]*(H*W//D+(H*W%D>=i)) for i in range(1,D+1)]
for i in range(D,H*W):
  n=i+1
  L[n%D-1][(n-1)//D]=L[n%D-1][(n-1)//D-1]+abs(A[i][1]-A[i-D][1])+abs(A[i][0]-A[i-D][0])

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

Submission status: Accepted

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

dx = [0 for _ in range(h*w+5)]
dy = [0 for _ in range(h*w+5)]

for i in range(h):
    for j in range(w):
        dx[a[i][j]] = i
        dy[a[i][j]] = j

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

for i in range(d+1,h*w+1):
        dfromd[i] = dfromd[i-d]+abs(dx[i-d]-dx[i])+abs(dy[i-d]-dy[i])

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

Submission status: Accepted

Solution code:
import sys
import numpy as np
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def main():

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

    a = [(0, (0, 0))]
    for i in range(H):
        a.extend([(element, [i, w]) for w, element in enumerate(A[i])])

    a.sort()
    tmp, number = zip(*a)
    number = np.array(number)
    x = np.resize(number[:, 0], (H * W // D + 1, D))
    y = np.resize(number[:, 1], (H * W // D + 1, D))

    magic = np.abs(x[1:] - x[:-1]) + np.abs(y[1:] - y[:-1])
    np.cumsum(magic, axis=0, out=magic)

    for L, R in zip(LR, LR):
        if L != R:
            q1 = R // D - 1
            q2 = L // D - 1
            r = R % D
            if q2 == -1:
                print(magic[q1][r])
            else:
                print(magic[q1][r] - magic[q2][r])
        else:
            print(0)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

a = [(0, (0, 0))]
for i in range(H):
    a.extend([(element, [i, w]) for w, element in enumerate(A[i])])

a.sort()
tmp, number = zip(*a)
number = np.array(number)
x = np.resize(number[:, 0], (H * W // D + 1, D))
y = np.resize(number[:, 1], (H * W // D + 1, D))

magic = np.abs(x[1:] - x[:-1]) + np.abs(y[1:] - y[:-1])
np.cumsum(magic, axis=0, out=magic)

for L, R in zip(LR, LR):
    if L != R:
        q1 = R // D - 1
        q2 = L // D - 1
        r = R % D
        if q2 == -1:
            print(magic[q1][r])
        else:
            print(magic[q1][r] - magic[q2][r])
    else:
        print(0)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')

H, W, D = LI()
data = H*W
cur = int(0)
A = [LI() for _ in range(H)]
ALocat = [None]*(data+1)
a = -1
for i in A:
    a +=1
    b = 0
    for j in i:
        ALocat[j] = [a, b]
        b +=1

#print(ALocat)
ALocat[0] = [0,0]
movecost = [0]*(data+1)
for i in range(D,data+1):
    movecost[i] = movecost[i-D] + abs(ALocat[i][0]-ALocat[i-D][0])\
                                + abs(ALocat[i][1]-ALocat[i-D][1])

#print(movecost)
ans = []
Q = I()
for _ in range(Q):
    L, R = LI()
    cur = movecost[R]-movecost[L]
    ans.append(cur)
for v in ans:
    print(v)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
h,w,d=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)]
li=[[] for i in range(d)]
for i in range(h):
    for j in range(w):
        li[a[i][j]%d].append([a[i][j],i,j])

for i in range(d):
    li[i].sort()

# print(li)
c=[[0]*(len(li[i])+1) for i in range(d)]

for i in range(d):
    for j in range(1,len(li[i])):
        c[i][j+1]=c[i][j]+abs(li[i][j-1][1]-li[i][j][1])+abs(li[i][j-1][2]-li[i][j][2])
# print(c)

for i in range(q):
    ama=lr[i][0]%d
    print(c[ama][(lr[i][1]+d-1)//d]-c[ama][(lr[i][0]+d-1)//d])

Submission status: Accepted

Solution code:
H,W,D = map(int,input().split())
A = []
for j in range(H):
  for i, a in enumerate(map(int,input().split())):
    A.append([a,i,j])
A.sort()
lenA = len(A)

points = [0] * lenA
for inia in [i for i in range(D)]:
  i = inia + D
  while i < lenA:
    points[i] = points[i-D] + abs(A[i][1]-A[i-D][1]) + abs(A[i][2]-A[i-D][2])
    i += D

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

Submission status: Accepted

Solution code:
from sys import stdin
H,W,D = [int(x) for x in stdin.readline().rstrip().split()]
data = [0]*(H*W+1)
for i in range(H):
    for j,A in enumerate([int(x) for x in stdin.readline().rstrip().split()]):
        data[A] = (i,j)
dp = [0]*(H*W+1)
for j in range(H*W+1):
    if j > D:
        dp[j] = dp[j-D] + abs(data[j][0]-data[j-D][0]) + abs(data[j][1]-data[j-D][1])
Q = int(stdin.readline().rstrip())
for _ in range(Q):
    L,R = [int(x) for x in stdin.readline().rstrip().split()]
    print(dp[R]-dp[L])

Submission status: Accepted

Solution code:
h,w,d=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)]
data=[[[0,0]]*(h*w//d+1) for i in range(d)]
for i in range(h):
    for j in range(w):
        b=a[i][j]%d
        c=a[i][j]//d
        data[b][c]=[i, j]
lst=[[0]*(h*w//d+1) for i in range(d)]
for i in range(d):
    for j in range(1,h*w//d+1):
        x,y=data[i][j]
        X,Y=data[i][j-1]
        lst[i][j]=lst[i][j-1]+abs(x-X)+abs(y-Y)
for u in lr:
    l,r=u
    b=l%d
    c=l//d
    e=r//d
    ans=lst[b][e]-lst[b][c]
    print(ans)

Submission status: Accepted

Solution code:
import sys
import bisect
h, w, d = [int(i) for i in sys.stdin.readline().split()]
a_ls = []
for y in range(h):
    a = [int(i) for i in sys.stdin.readline().split()]
    for x in range(w):
        a_ls += [(a[x], x, y)]

a_ls.sort(key=lambda x:x[0])
diff_ls = []
for ind in range(h*w):
    if ind < d:
        diff_ls.append(0)
    else:
        start = a_ls[ind-d]
        goal = a_ls[ind]
        diff = diff_ls[ind-d] + abs(start[2] - goal[2]) + abs(start[1] - goal[1])
        diff_ls.append(diff)
q = int(input())
for j in range(q):
    l, r = [int(i) for i in sys.stdin.readline().split()]
    l -= 1
    r -= 1
    print(diff_ls[r] - diff_ls[l])

Submission status: Accepted

Solution code:
H,W,D=map(int,input().split())
l=[[] for r in range(D)]

for i in range(1,H+1):
    Ai=list(map(int,input().split()))
    for j,Aij in enumerate(Ai):
        l[Aij%D].append((Aij,i,j+1))

for lr in l:
    lr.sort()

# print(l)

d=[]
for r in range(D):
    lr=[]
    for i in range(len(l[r])-1):
        lr.append(abs(l[r][i][1]-l[r][i+1][1])+abs(l[r][i][2]-l[r][i+1][2]))
    d.append(lr)

# print(d)

s=[]
for r in range(D):
    sr=[0]
    for i in range(len(d[r])):
        sr.append(sr[i]+d[r][i])
    s.append(sr)

# print(s)

Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    r=L%D
    left=(L-r)//D-(1 if r==0 else 0)
    right=(R-r)//D-(1 if r==0 else 0)

    print(s[r][right]-s[r][left])

Submission status: Accepted

Solution code:
h,w,d = map(int,input().split())
arr = []
for i in range(h):
    tmp_list = list(map(int,input().split()))
    arr.append(tmp_list)
q = int(input())
querry = []
for i in range(q):
    querry.append(list(map(int,input().split())))
num_list = [[0]*2 for i in range(h*w + 1)]
for i in range(h):
    for j in range(w):
        num_list[arr[i][j]] = [i,j]
cost_list = [0]*(h*w + 1)
for i in range(1,h*w):
    for r in range(h*w):
        if i > h*w - d:
            break
        if cost_list[i + d] == 0:
            x0 = num_list[i][0]
            x1 = num_list[i + d][0]
            y0 = num_list[i][1]
            y1 = num_list[i + d][1]
            cost_list[i + d] += cost_list[i] + abs(x0-x1) +  abs(y0-y1)
        else:
            break
        i += d
for l,r in querry:
    print(cost_list[r] - cost_list[l])

Submission status: Accepted

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

L = [0]*(H*W+1)
for i in range(H):
    for j in range(W):
        L[A[i][j]] = [i, j]
        
E = [0]*(H*W+1)
for i in range(D+1, H*W+1):
    E[i] = E[i-D] + abs(L[i][0]-L[i-D][0])+abs(L[i][1]-L[i-D][1])
    
for i in range(Q):
    ans = 0
    l, r = map(int, input().split())
    ans = E[r] - E[l]
    print(ans)

Submission status: Accepted

Solution code:
h,w,d=map(int,input().split())
e={}
ans=[0]*(h*w+1)
for i in range(1,h+1):
    a=list(map(int,input().split()))
    for j in range(w):
        e[a[j]]=(i,j+1)
for i in range(d+1,h*w+1):
    x,y=e[i]
    c,v=e[i-d]
    ans[i]=abs(x-c)+abs(y-v)+ans[i-d]

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
#import heapq
#from fractions import gcd
#from collections import defaultdict
#sys.setrecursionlimit(10**9)
#map(int,input().split())




def main():
    h,w,D=map(int,input().split())
    li=[0]*(h*w+1)
    kyori=[0]*(h*w+1)
    for i in range(h):
        A=list(map(int,input().split()))
        for j in range(w):
            li[A[j]]=(i+1,j+1)

    for i in range(D+1,h*w+1):
        kyori[i]=kyori[i-D]+abs(li[i][0]-li[i-D][0])+abs(li[i][1]-li[i-D][1])

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

dic = {}
K = H*W//D
memo = [[0]* (K+1) for _ in range(D+1)]

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

for extra in range(H*W+1, H*W+2*D):
    dic[extra] = [0, 0]

for i in range(1, D+1):
    for j in range(K):
        x, y = dic[i+D*j]
        nx, ny = dic[i+D*(j+1)]
        cost = abs(x-nx) + abs(y-ny)
        memo[i][j+1] = memo[i][j] + cost

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
H, W, D = [int(_) for _ in input().split()]
l1 = [0] * H
for i in range(0, H):
    l1[i] = [int(_) for _ in input().split()]
Q = int(input())
l2 = [0] * Q
for i in range(0, Q):
    l2[i] = [int(_) for _ in input().split()]


HWdict = {}
for j in range(0, H):
    for k in range(0,W):
        HWdict[l1[j][k]] = [j, k]


mylist = []
for i in range(0,D):
    mylist.append({})

for i in range(0, D):
    j = 1
    mylist[i][i+1] = 0
    while ((i+1) + j*D) <= H*W:
        mylist[i][(i+1) + j*D] = mylist[i][(i+1)+ (j-1)*D] + abs(HWdict[(i+1) + j*D][0]- HWdict[(i+1) + (j-1)* D][0]) + abs(HWdict[(i+1) + j*D][1] - HWdict[(i+1) + (j-1)* D][1])
        j += 1

L = 0
R = 0
ans = 0
for i in range(0, Q):
    L = l2[i][0]
    R = l2[i][1]
    print(mylist[R%D-1][R] - mylist[R%D-1][L])

Submission status: Accepted

Solution code:
import sys
import itertools
from itertools import accumulate
def main():
    input = sys.stdin.readline
    def inputs():return [int(x) for x in input().split()]
    H,W,D = inputs()
    w = [[None]*W for i in range(H)]
    A = []
    for i in  range(H):
        B = inputs()
        A.append(B)
    E={i:[] for i in range(1,H*W+1)}
    for i in range(H):
        for j in range(W):
            a = A[i][j]
            if a<=H*W:
                E[a].append((i+1,j+1))
    #print(E)
    dis = [0]*(H*W+1)
    for i in range(1,H*W+1):
        if i+D<=H*W:
            #print(i+D)
            x = E[i][0][0]
            y = E[i][0][1]
            a = E[i+D][0][0]
            b = E[i+D][0][1]
            dis[i+D] = dis[i]+abs(a-x)+abs(b-y)
    Q = int(input())
    for i in range(Q):
        r,l = inputs()
        print(dis[l]-dis[r])
main()

Submission status: Accepted

Solution code:
H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for i in range(H)]
Q = int(input())
S = [list(map(int,input().split())) for i in range(Q)]
P = [None]*(H*W+1)
for i in range(H):
    for j in range(W):
        P[A[i][j]] = [i,j]

Accum = [0]*(H*W+1)
accum = 0

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

for s in S:
    print(Accum[s[1]]-Accum[s[0]])

Submission status: Accepted

Solution code:
H,W,D = map(int,input().split())
Point = {}
for y in range(H) :
    line = list(map(int,input().split()))
    for x,p in enumerate(line) :
        Point[p] = (y,x)

Q = int(input())

def dist(ny,nx,py,px) :
    return abs(ny-py) + abs(nx-px)

Cost = [0]*(H*W+1)
for i in range(D+1, H*W+1) :
    yi,xi = Point[i-D]
    yj,xj = Point[i]
    Cost[i] = Cost[i-D] + dist(yi,xi,yj,xj)


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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
h, w, d = map(int, input().split())
a = {}
l = list(range(1, h * w + 1))
for i in range(h):
  for j, x in enumerate(input().split()):
    a[int(x)] = (i, j)
memo = {}
def calc(s):
  tmp = 0
  memo[a[s+1]] = 0
  for Xc, Xn in zip(l[s::d], l[s+d::d]):
    xc, yc = a[Xc]
    xn, yn = a[Xn]
    tmp += abs(xc - xn) + abs(yc - yn)
    memo[a[Xn]] = tmp
for i in range(d):
  calc(i)
for _ in range(int(input())):
  l, r = map(int, input().split())
  print(memo[a[r]] - memo[a[l]])

Submission status: Accepted

Solution code:
H, W, D = map(int, input().split())
Board = [0] * (H*W+1)
path = [[0] for _ in range(D)] 
for h in range(H):
    A = list(map(int, input().split()))
    for w in range(W):
        Board[A[w]] = [w+1, h+1]
for i in range(1, D+1):
    d = i % D
    for j in range(i+D, H*W+1, D):
        path[d].append(path[d][(j+(D-1))//D-2] + abs(Board[j][0] - Board[j-D][0]) + abs(Board[j][1] - Board[j-D][1]))

for i in range(int(input())):
    L, R = map(int, input().split())
    d = L % D
    print(path[d][(R+(D-1))//D-1] - path[d][(L+(D-1))//D-1])

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

def main():
    # init
    h,w,d = map(int,input().split())
    dic = defaultdict(list)
    for i in range(h):
        nums = [int(x) for x in input().split()]
        for j,num in enumerate(nums):
            dic[int(num)] = [i,j]
    # memo
    ls = [0 for i in range(w*h+1)]
    for i in range(d+1,w*h+1):
        before,after = dic[i-d],dic[i]
        diff = abs(after[0]-before[0]) + abs(after[1]-before[1])
        ls[i] = ls[i-d]+ diff
    # ans
    q = int(input())
    for i in range(q):
        l,r = map(int,input().split())
        print(ls[r]-ls[l])
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

def main():
    # init
    input = sys.stdin.readline
    h,w,d = map(int,input().split())
    dic = defaultdict(list)
    for i in range(h):
        nums = [int(x) for x in input().split()]
        for j,num in enumerate(nums):
            dic[int(num)] = [i,j]
    # memo
    ls = [0 for i in range(w*h+1)]
    for i in range(d+1,w*h+1):
        before,after = dic[i-d],dic[i]
        diff = abs(after[0]-before[0]) + abs(after[1]-before[1])
        ls[i] = ls[i-d]+ diff
    # ans
    q = int(input())
    for i in range(q):
        l,r = map(int,input().split())
        print(ls[r]-ls[l])
if __name__ == "__main__":
    main()