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: Runtime Error

Solution code:
tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dict = {}
for i in range(H):
    tmp = input().split()
    for d in range(W):
        dict[tmp[d]] = str(i)+' '+str(d)
result ={}
cost ={}
dict[0] = 0
def calcost(L,R,D):
    if int(R)<=D:
        cost[R] = 0
        return 0
    else:
        posi1 = dict[R].split()
        posi2 = dict[str(int(R)-D)].split()
        costs = abs(int(posi2[0])-int(posi1[0])) + abs(int(posi2[1])-int(posi1[1]))
        if str(int(R)-D) in cost:
            cost[R] = costs + cost[str(int(R)-D)]
            return cost[R]
        else:
            cost[R] = costs + calcost(L,str(int(R)-D),D)
            return cost[R]

for n in range(D+1,H*W+1):
    calcost(str(1),str(n),D)

Q = int(input())
for j in range(Q):
    tmpx = input()
    if tmpx in result:
        print(result[tmpx])
    else:
        tmp = tmpx.split()
        result[tmpx] = cost[tmp[1]]-cost[tmp[0]]
        print(result[tmpx])

Submission status: Runtime Error

Solution code:
tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dict = {}
for i in range(H):
    tmp = input().split()
    for d in range(W):
        dict[tmp[d]] = str(i)+' '+str(d)
result ={}
cost ={}

def calcost(L,R,D):
    if int(R)<=D:
        cost[R] = 0
        return 0
    else:
        posi1 = dict[R].split()
        posi2 = dict[str(int(R)-D)].split()
        costs = abs(int(posi2[0])-int(posi1[0])) + abs(int(posi2[1])-int(posi1[1]))
        if str(int(R)-D) in cost:
            cost[R] = costs + cost[str(int(R)-D)]
            return cost[R]
        else:
            cost[R] = costs + calcost(L,str(int(R)-D),D)
            return cost[R]

for n in range(D+1,H*W+1):
    calcost(str(1),str(n),D)

Q = int(input())
for j in range(Q):
    tmpx = input()
    if tmpx in result:
        print(result[tmpx])
    else:
        tmp = tmpx.split()
        result[tmpx] = cost[tmp[1]]-cost[tmp[0]]
        print(result[tmpx])

Submission status: Runtime Error

Solution code:
tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dict = {}
for i in range(H):
    tmp = input().split()
    for d in range(W):
        dict[tmp[d]] = str(i)+' '+str(d)
result ={}
cost ={}

def calcost(L,R,D):
    if int(R)<=D:
        cost[R] = 0
        return 0
    else:
        posi1 = dict[R].split()
        posi2 = dict[str(int(R)-D)].split()
        costs = abs(int(posi2[0])-int(posi1[0])) + abs(int(posi2[1])-int(posi1[1]))
        if str(int(R)-D) in cost:
            cost[R] = costs + cost[str(int(R)-D)]
            return cost[R]
        else:
            cost[R] = costs + calcost(L,str(int(R)-D),D)
            return cost[R]

for n in range(D+1,H*W+1):
    calcost(str(1),str(n),D)

Q = int(input())
for j in range(Q):
    tmpx = input()
    if tmpx in result:
        print(result[tmpx])
    else:
        tmp = tmpx.split()
        result[tmpx] = cost[tmp[1]]-cost[tmp[0]]
        print(result[tmpx])
print(cost)

Submission status: Runtime Error

Solution code:
tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dict = {}
for i in range(H):
    tmp = input().split()
    for d in range(W):
        dict[tmp[d]] = str(i)+' '+str(d)
result ={}
cost ={}
def calcost(L,R,D):
    if int(R)<D:
        cost[R]=0
        return 0
    elif (int(R)-int(L))<D:
        return 0
    else:
        posi1 = dict[R].split()
        posi2 = dict[str(int(R)-D)].split()
        costs = abs(int(posi2[0])-int(posi1[0])) + abs(int(posi2[1])-int(posi1[1]))
        cost[R] = costs
        return costs + calcost(L,str(int(R)-D),D)

for n in range(1,H*W):
    calcost(str(1),str(n),D)

Q = int(input())
for j in range(Q):
    tmpx = input()
    if tmpx in result:
        print(result[tmpx])
    else:
        tmp = tmpx.split()
        result[tmpx] = cost[tmp[1]]-cost[tmp[0]]
        print(result[tmpx])

Submission status: Runtime Error

Solution code:
tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dict = {}
for i in range(H):
    tmp = input().split()
    for d in range(W):
        dict[tmp[d]] = str(i)+' '+str(d)
result ={}
cost ={}
def calcost(L,R,D):
    if int(R)<D:
        cost[R]=0
        return 0
    elif (int(R)-int(L))<D:
        return 0
    else:
        posi1 = dict[R].split()
        posi2 = dict[str(int(R)-D)].split()
        costs = abs(int(posi2[0])-int(posi1[0])) + abs(int(posi2[1])-int(posi1[1]))
        cost[R] = costs
        return costs + calcost(L,str(int(R)-D),D)

for n in range(1,H*W):
    calcost(1,n,D)

Q = int(input())
for j in range(Q):
    tmpx = input()
    if tmpx in result:
        print(result[tmpx])
    else:
        tmp = tmpx.split()
        result[tmpx] = cost[tmp[1]]-cost[tmp[0]]
        print(result[tmpx])

Submission status: Runtime Error

Solution code:
H, W, D = tuple(map(int, input().split()))
board = dict()
for h in range(H):
    row = tuple(map(int, input().split()))
    for w in range(W):
        board[row[w]] = (h, w)
delta = dict([(i, 0) for i in range(1, D+1)])
for d in range(D+1, H*W):
    delta[d] = delta[d-D] + abs(board[d][0] - board[d-D][0]) + abs(board[d][1] - board[d-D][1])

Q = int(input())

LRs = [tuple(map(int, input().split())) for _ in range(Q)]
result = [delta[LR[1]] - delta[LR[0]] for LR in LRs]

for r in result:
    print(r)

Submission status: Runtime Error

Solution code:
tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dict = {}
for i in range(H):
    tmp = input().split()
    for d in range(W):
        dict[tmp[d]] = str(i)+' '+str(d)
result ={}
def calcost(L,R,D):
    if int(R)<D or (int(R)-int(L))<D:
        return 0
    else:
        posi1 = dict[R].split()
        posi2 = dict[str(int(R)-D)].split()
        costs = abs(int(posi2[0])-int(posi1[0])) + abs(int(posi2[1])-int(posi1[1]))
        search_w = L +' '+str(int(R)-D)
        if search_w in result:
            return costs + result[search_w]
        else:
            return costs + calcost(L,str(int(R)-D),D)

Q = int(input())
for j in range(Q):
    tmpx = input()
    if tmpx in result:
        print(result[tmpx])
    else:
        tmp = tmpx.split()
        result[tmpx] = calcost(tmp[0],tmp[1],D)
        print(result[tmpx])

Submission status: Runtime Error

Solution code:
tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dict = {}
for i in range(H):
    tmp = input().split()
    for d in range(W):
        dict[tmp[d]] = str(i)+' '+str(d)

def calcost(L,R,D):
    if int(R)<D or (int(R)-int(L))<D:
        return 0
    else:
        posi1 = dict[R].split()
        posi2 = dict[str(int(R)-D)].split()
        costs = abs(int(posi2[0])-int(posi1[0])) + abs(int(posi2[1])-int(posi1[1]))
        return costs + calcost(L,str(int(R)-D),D)

cost = {}
result ={}
Q = int(input())
for j in range(Q):
    tmpx = input()
    if tmpx in result:
        print(result[tmpx])
    else:
        tmp = tmpx.split()
        result[tmpx] = calcost(tmp[0],tmp[1],D)
        print(result[tmpx])

Submission status: Runtime Error

Solution code:
tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dict = {}
for i in range(H):
    tmp = input().split()
    for d in range(W):
        dict[tmp[d]] = str(i)+' '+str(d)

def calcost(L,R,D):
    if int(R)<=D or (int(R)-int(L))<D:
        return 0
    else:
        posi1 = dict[R].split()
        posi2 = dict[str(int(R)-D)].split()
        costs = abs(int(posi2[0])-int(posi1[0])) + abs(int(posi2[1])-int(posi1[1]))
        return costs + calcost(L,str(int(R)-D),D)

cost = {}
result ={}
Q = int(input())
for j in range(Q):
    tmpx = input()
    if tmpx in result:
        print(result[tmpx])
    else:
        tmp = tmpx.split()
        result[tmpx] = calcost(tmp[0],tmp[1],D)
        print(result[tmpx])

Submission status: Runtime Error

Solution code:
tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dict = {}
for i in range(H):
    tmp = input().split()
    list[i] =tmp
    for d in range(W):
        dict[list[i][d]] = str(i)+' '+str(d)
cost = {}

def calcost(L,R,D):
    if int(R)<=D or (int(R)-int(L))<D:
        return 0
    else:
        if str(int(R)-D) in cost:
            return cost[str(int(R)-D)] + calcost(L,str(int(R)-D),D)
        else:
            posi1 = dict[R].split()
            posi2 = dict[str(int(R)-D)].split()
            costs = abs(int(posi2[0])-int(posi1[0])) + abs(int(posi2[1])-int(posi1[1]))
            cost[str(int(R)-D)] = costs
            return costs + calcost(L,str(int(R)-D),D)

Q = int(input())
for j in range(Q):
    tmp = input().split()
    print(calcost(tmp[0],tmp[1],D))

Submission status: Runtime Error

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

comp = {}
for i in range(h):
    tmp = list(map(int, input().split(' ')))
    for j in range(w):
        comp[tmp[j]] = [i, j]

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

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

Submission status: Runtime Error

Solution code:
line = input().split(" ")
a = list(map(int, line))
data = [0] * 90001
ans = 0
for i in range(0, a[0]):
    line = input().split(" ")
    temp = list(map(int, line))
    for j in range(0, a[1]):
        data[temp[j]] = [i, j]

memo = [0] * 90001

for i in range(0, a[0] * a[1]):
    if i < a[2]:
        memo[i] = 0
    else:
        memo[i] = memo[i - a[2]] + abs(data[i][0] - data[i - a[2]][0]) + abs(data[i][1] - data[i - a[2]][1])
times = int(input())
for i in range(0, times):
    line = list(map(int, input().split(" ")))
    print(memo[line[1]-1] - memo[line[0]-1])

Submission status: Runtime Error

Solution code:
line = input().split(" ")
a = list(map(int, line))
data = [0] * 90001
ans = 0
for i in range(0, a[0]):
    line = input().split(" ")
    temp = list(map(int, line))
    for j in range(0, a[1]):
        data[temp[j]] = [i, j]

memo = [0] * 90001

for i in range(0, a[0] * a[1]):
    if i < a[2]:
        memo[i] = 0
    else:
        memo[i] = memo[i - a[2]] + abs(data[i][0] - data[i - a[2]][0]) + abs(data[i][1] - data[i - a[2]][1])
times = int(input())
for i in range(0, times):
    line = list(map(int, input().split(" ")))
    print(memo[line[1]] - memo[line[0]])

Submission status: Runtime Error

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

dic = {}
for i in range(H):
    for j,v in enumerate(list(map(int, input().split()))):
        dic[v] = (i,j)

Q = int(input())

Qs = []
mi = 1000000
ma = 1
for i in range(Q):
    l,r = list(map(int, input().split()))
    Qs.append((l,r))
    mi = min(mi, l)
    ma = max(ma, r)

S = [0 for i in range(100000)]
acm = 0
pi, pj = dic[mi]
for i in range(mi, ma+D, D):
    x,y = dic[i]
    acm += abs(x-pi) + abs(y-pj)
    S[i] = acm
    pi,pj = x,y

for i in Qs:
    l,r = i
    print(S[r] - S[l])

Submission status: Runtime Error

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

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

Q = int(input())

Qs = []
mi = 10000000
ma = 1
for i in range(Q):
    l,r = list(map(int, input().split()))
    Qs.append((l,r))
    mi = min(mi, l)
    ma = max(ma, r)

S = [0 for i in range(100000)]
acm = 0
pi, pj = dic[mi]
for i in range(mi, ma+D, D):
    x,y = dic[i]
    acm += abs(x-pi) + abs(y-pj)
    S[i] = acm
    pi,pj = x,y

for i in Qs:
    l,r = i
    print(S[r] - S[l])

Submission status: Runtime Error

Solution code:
import sys
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())

H,W,D = Is()
d = dict()
for i in range(H):
    s = Is()
    for j,e in enumerate(s):
        d[e] = (i,j)
m = [0]*(H*W*1)
for i in range(D+1,H*W*1):
    m[i] = m[i-D] + abs(d[i-D][0] - d[i][0]) + abs(d[i-D][1] - d[i][1])

Q = I()
for q in range(Q):
    l,r = Is()
    print(m[r]-m[l])

Submission status: Runtime Error

Solution code:
h, w, D = map(int, input().split())
a = []
p = {}
for i in range(h):
  temp = list(map(int, input().split()))
  a.append(temp)
  for j in range(w):
    p[temp[j]] = (i, j)
  

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

d = {}
for i in range(D+1, h*w+1):
  if i-D <= 0:
    d[i-D] = 0
    p[i-D] = p[i]
  d[i] = d[i-D] + abs(p[i][0]-p[i-D][0]) + abs(p[i][1]-p[i-D][1])

for i in range(q):
  print(d[R[i]]-d[L[i]])

Submission status: Runtime Error

Solution code:
h, w, D = map(int, input().split())
a = []
p = {}
for i in range(h):
  temp = list(map(int, input().split()))
  a.append(temp)
  for j in range(w):
    p[temp[j]] = (i, j)
  

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

d = {}
for i in range(D+1, h*w+1):
  if i-D not in d:
    d[i-D] = 0
  d[i] = d[i-D] + abs(p[i][0]-p[i-D][0]) + abs(p[i][1]-p[i-D][1])

for i in range(q):
  print(d[R[i]]-d[L[i]])

Submission status: Runtime Error

Solution code:
h, w, D = map(int, input().split())
a = []
p = {}
for i in range(h):
  temp = list(map(int, input().split()))
  a.append(temp)
  for j in range(w):
    p[temp[j]] = (i, j)
  

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

d = {}
for i in range(D+1, h*w+1):
  if not i-D in d:
    d[i-D] = 0
  d[i] = d[i-D] + abs(p[i][0]-p[i-D][0]) + abs(p[i][1]-p[i-D][1])

for i in range(q):
  print(d[R[i]]-d[L[i]])

Submission status: Runtime Error

Solution code:
h, w, d = (int(i) for i in input().split())
arr = [[int(i) for i in input().split()] for y in range(h)]

q = int(input())

for i in range(q):
    res = 0
    count = 0
    start, end = (int(j) for j in input().split())
    for n in range(start, end+d, d):
        for x in range(w):
            for y in range(h):
                if arr[x][y] == n:
                    idx = [x, y]
                    break
        if count >= 1:
            res += abs(idx[0]-idx_tmp[0]) + abs(idx[1]-idx_tmp[1])
        idx_tmp = idx
        count += 1
    print(res)

Submission status: Runtime Error

Solution code:
def ACBC_089_D():
    _hwd = str(input()).split()
    _hwd = list(map(int, _hwd))
    _area = []
    _lrs = []
    _mpcount = 0

    for i in range(0, _hwd[0]):
        _aij = str(input()).split()
        _area += list(map(int, _aij))

    _q = int(input())

    for i in range(0, _q):
        _lr = str(input().split())
        _lrs += list(map(int, _lr))

    for i in range(0, _q):
        for i in range(0, int((_lrs[_q][1] - _lrs[_q][0]) / _hwd[2])):
            for j in range(0, _hwd[0]):
                if _lrs[_q][0] + _hwd[2] * i in _area[j]:
                    if not i:
                        _nowx = _area[i].index(_lrs[_q][0])
                        _nowy = j
                    _nextx = _area[i].index(_lrs[_q][0] + _hwd[2] * i)
                    _nexty = j
            _mpcount += (_nextx + _nexty - _nowx - _nowy)
            _nowx = _nextx
            _nowy = _nexty
    print(_mpcount)


ACBC_089_D()

Submission status: Runtime Error

Solution code:
import numpy as np

H, W, D = map(int, input().split())
pos = [None]*(H*W)

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

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    if L == R:
        print(0)
    else:
        to_be_checked = [i for i in range(L, R+1, D)]
        moves = len(to_be_checked)
        pos_list = [tpl for tpl in to_be_checked]

        MP = sum([np.absolute(pos_list[i][0] - pos_list[i+1][0]) for i in range(moves-1)]) + sum([np.absolute(pos_list[i][1] - pos_list[i+1][1]) for i in range(moves-1)])

        print(MP)

Submission status: Runtime Error

Solution code:
import sys
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())

H,W,D = Is()
d = dict()
for i in range(H):
    s = Is()
    for j,e in enumerate(s):
        d[e] = (i,j)
m = [0]*H*W
for i in range(D+1,H*W):
    m[i] = m[i-D] + abs(d[i-D][0] - d[i][0]) + abs(d[i-D][1] - d[i][1])

Q = I()
for q in range(Q):
    l,r = Is()
    print(m[r]-m[l])

Submission status: Runtime Error

Solution code:

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

coord_dict_x = [0 for i in range(90001)]
coord_dict_y = [0 for i in range(90001)]

for i in range(H):
    gyo = [int(i) for i in input().split()]
    for j in range(W):
        coord_dict_x[gyo[j]] = i
        coord_dict_y[gyo[j]] = j

Q = int(input())
exam = [[int(i) for i in input().split()] for i in range(Q)]

for i in range(Q):
    reduce_MP = 0
    num = exam[i][0]
    coord1_x = coord_dict_x[num]
    coord1_y = coord_dict_y[num]
    while num < exam[i][1]:
        num += D
        coord2_x = coord_dict_x[num]
        coord2_y = coord_dict_y[num]
        reduce_MP += abs(coord1_x - coord2_x) + abs(coord1_y - coord2_y)
        coord1 = coord2
    print(reduce_MP)

Submission status: Runtime Error

Solution code:
import numpy as np
H, W, D=list(map(int,input().split(" ")))
#print(in1)
#arr=np.zeros((in1[0],in1[1]))
d={}
for i in range(H):
    #arr[i]=input().split(" ")
    for n,k in enumerate(input().split(" ")):
        d[int(k)]=[i,n]
#print(arr)
Q=int(input())
out=[]

cost={}
for i in range(1,D+1):
    now = i + D
    cost[i]=abs(d[now][0] - d[now - D][0]) + abs(d[now][1] - d[now - D][1])
    while now <= H * W:
        cost[now] = cost[now - D] + abs(d[now][0] - d[now - D][0]) + abs(d[now][1] - d[now - D][1])
        now += D


out=[]
for k in range(Q):
    start,end=list(map(int,input().split(" ")))
    out.append(cost[end]-cost[start])

for i in out:
    print(int(i))

Submission status: Runtime Error

Solution code:
import numpy as np
H, W, D=list(map(int,input().split(" ")))
#print(in1)
#arr=np.zeros((in1[0],in1[1]))
d={}
for i in range(H):
    #arr[i]=input().split(" ")
    for n,k in enumerate(input().split(" ")):
        d[int(k)]=[i,n]
#print(arr)
Q=int(input())
out=[]

cost={}
for i in range(1,D+1):
    now = i + D
    cost[i]=abs(d[now][0] - d[now - D][0]) + abs(d[now][1] - d[now - D][1])
    while now <= H * W:
        cost[now] = cost[now - D] + abs(d[now][0] - d[now - D][0]) + abs(d[now][1] - d[now - D][1])
        now += D


out=[]
for k in range(Q):
    start,end=list(map(int,input().split(" ")))
    out.append(cost[end]-cost[start])
for i in out:
    print(i)

Submission status: Runtime Error

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)]
d = [0] * (H*W)
num_dict = {}
y = 0
for aa in A:
    x = 0
    for a in aa:
        num_dict[a] = [x, y]
        x += 1
    y += 1

for i in range(D+1, H*W):
    d[i] = d[i-D] + abs(num_dict[i][0]-num_dict[i-D][0]) + abs(num_dict[i][1]-num_dict[i-D][1])
for l, r in LR:
    print(d[r]-d[l])

Submission status: Runtime Error

Solution code:

H, W, D = [int(x) for x in input().strip().split(' ')]
stage = {}
for i in range(H):
    nums = [int(x) for x in input().strip().split(' ')]
    for j in range(W):
        stage[nums[j]] = [i + 1, j + 1]
Q = int(input())
tests = []
for _ in range(Q):
    tests.append([int(x) for x in input().strip().split(' ')])

scores = []
done = {}
for i in range(Q):
    L, R = tests[i]
    if (L, R) in done:
        scores.append(done[(L, R)])
    elif L == R:
        scores.append(0)
    else:
        x, y = stage[L]
        score = 0
        nowL = L.copy()
        while nowL < R:
            if (nowL, R) in done:
                score += done[(nowL, R)]
                break
            new_x, new_y = stage[nowL + D]
            score += abs(new_x - x) + abs(new_y - y)
            x = new_x
            y = new_y
            nowL += D
        scores.append(score)
        done[(L, R)] = score

for score in scores:
    print(score)

Submission status: Runtime Error

Solution code:
import numpy as np

H, W, D = [int(a) for a in input().split()]

a = np.zeros([H*W+1, 2], dtype=int)
for i in range(H):
    a_ = np.array([int(a) for a in input().split()])
    for j in range(W):
        a[a_[j], 0] = i
        a[a_[j], 1] = j

memo = np.zeros([H*W+1, H*W+1], dtype=int)

Q = int(input())
ans = []

def func(c, r):
    if memo[c][r] != 0:
        p = memo[c][r]
    else:
        if c == r:
            p = 0
        else:
            c_ = c + D
            p = func(c_, r)
            p += abs(a[c][0] - a[c_][0]) + abs(a[c][1] - a[c_][1])
        memo[c][r] = p
    return p
    

for i in range(Q):
    l, r = [int(a) for a in input().split()]
    c = l
    p = func(l, r)
    memo[l][r] = p

    ans.append(p)
for ans_ in ans:
    print(ans_)

Submission status: Runtime Error

Solution code:
import numpy as np

H, W, D = [int(a) for a in input().split()]

a = np.zeros([H*W+1, 2], dtype=int)
for i in range(H):
    a_ = np.array([int(a) for a in input().split()])
    for j in range(W):
        a[a_[j], 0] = i
        a[a_[j], 1] = j

#memo = np.zeros([H*W+1, H*W+1], dtype=int)
memo = {}

Q = int(input())
ans = []

def func(c, r):
    try:
        p = memo[c][r]
    except:
        if c == r:
            p = 0
        else:
            c_ = c + D
            p = func(c_, r)
            p += abs(a[c][0] - a[c_][0]) + abs(a[c][1] - a[c_][1])
        try:
            memo[c][r] = p
        except:
            memo[c] = {}
            memo[c][r] = p
    return p
    

for i in range(Q):
    l, r = [int(a) for a in input().split()]
    c = l
    p = func(l, r)
    try:
        memo[l][r] = p
    except:
        memo[l] = {}
        memo[l][r] = p

    ans.append(p)
for ans_ in ans:
    print(ans_)