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:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

h,w,d = li()
a = [list(li()) for _ in range(h)]

num2point = [(-1,-1)]*(h*w+1)
for r, ai in enumerate(a):
    for c, aij in enumerate(ai):
        num2point[aij] = (r, c)
    

dist = [[] for _ in range(d)]
for num in range(h*w):
    i = num+1
    if i // d == 0 or i == d:
        dist[i%d].append(0)
        
    else:
        dist[i%d].append(abs(num2point[i][0]-num2point[i-d][0]) + abs(num2point[i][1]-num2point[i-d][1]))
        
dist_cum = [list(accumulate(dist_row)) for dist_row in dist]


q = ni()
for _ in range(q):
    l,r = li()
    print(dist_cum[l%d][r//d] - dist_cum[l%d][l//d])

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

h,w,d = li()
a = [list(li()) for _ in range(h)]

num2point = [(-1,-1)]*(h*w+1)
for r, ai in enumerate(a):
    for c, aij in enumerate(ai):
        num2point[aij] = (r, c)
    

dist = [[] for _ in range(d)]
for num in range(h*w):
    i = num+1
    if i // d == 0:
        dist[i%d].append(0)
        
    else:
        dist[i%d].append(abs(num2point[i][0]-num2point[i-d][0]) + abs(num2point[i][1]-num2point[i-d][1]))
        
dist_cum = [list(accumulate(dist_row)) for dist_row in dist]


q = ni()
for _ in range(q):
    l,r = li()
    print(dist_cum[l%d][r//d] - dist_cum[l%d][l//d])

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

h,w,d = li()
a = [list(li()) for _ in range(h)]

num2point = [(-1,-1)]*(h*w+1)
for r, ai in enumerate(a):
    for c, aij in enumerate(ai):
        num2point[aij] = (r, c)
    

dist = [[] for _ in range(d)]
for i in range(h*w):
    if i // d == 0 or i == d:
        dist[i%d].append(0)
        
    else:
        dist[i%d].append(abs(num2point[i][0]-num2point[i-d][0]) + abs(num2point[i][1]-num2point[i-d][1]))
        
dist_cum = [list(accumulate(dist_row)) for dist_row in dist]


q = ni()
for _ in range(q):
    l,r = li()
    print(dist_cum[l%d][r//d] - dist_cum[l%d][l//d])

Submission status: Runtime Error

Solution code:
h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]
q = int(input())
l = [list(map(int,input().split())) for _ in range(q)]
dic = {0:[0]}
for i in range(1,d+1):
    list = []
    for j in range(i,h*w,d):
        for y in range(len(a)):
            if j in a[y]:
                for x in range(len(a[y])):
                    if a[y][x]==j:
                        if i==j:
                            list.append(0)
                            x_ = x
                            y_ = y
                            k = 0
                        else:
                            k += abs(x-x_)+abs(y-y_)
                            list.append(k)
                            x_ = x
                            y_ = y
    dic[i] = list
print(dic)
for l_ in l:
    if l_[0]%d==0:
        print(dic[d][(l_[1]-l_[0])//d])
    else:
        print(dic[l_[0]%d][(l_[1]-l_[0])//d])

Submission status: Runtime Error

Solution code:
h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]
q = int(input())
l = [list(map(int,input().split())) for _ in range(q)]
dic = {}
for i in range(1,h*w):
    list = []
    for j in range(i,h*w,d):
        for y in range(len(a)):
            if j in a[y]:
                for x in range(len(a[y])):
                    if a[y][x]==j:
                        if i==j:
                            list.append(0)
                            x_ = x
                            y_ = y
                            k = 0
                        else:
                            k += abs(x-x_)+abs(y-y_)
                            list.append(k)
                            x_ = x
                            y_ = y
    dic[i] = list
for l_ in l:
    print(dic[l_[0]][(l_[1]-l_[0])//d])

Submission status: Runtime Error

Solution code:
#import numpy as np
#import math
def getInt(): return int(input())
def getIntList(): return [int(x) for x in input().split()]
def zeros(n): return [0]*n
def zeros2(n, m): return [zeros(m)]*n # obsoleted zeros((n, m))で代替
def getIntLines(n): return [int(input()) for i in range(n)]
def getIntMat(n, m):  # n行に渡って、1行にm個の整数
    mat = zeros2(n, m)
    for i in range(n):
        mat[i] = getIntList()
    return mat


ALPHABET = [chr(i+ord('a')) for i in range(26)]
DIGIT = [chr(i+ord('0')) for i in range(10)]
N1097 = 10**9 + 7
INF = 10**18


class Debug():
    def __init__(self):
        self.debug = True

    def off(self):
        self.debug = False

    def dmp(self, x, cmt=''):
        if self.debug:
            if cmt != '':
                print(cmt, ':  ', end='')
            print(x)
        return x


def prob():
    d = Debug()
    d.off()
    H, W, D = getIntList()
    d.dmp((H, W, D), 'H, W, D')
    A = getIntMat(H, W)
    d.dmp(A)
    p = zeros(H*W+1)
    for i in range(H):
        for j in range(W):
            p[A[i][j]] = [i,j]
    d.dmp(p)
    Q = getInt()
    d.dmp(Q)
    for i in range(Q):
        mp = 0
        L, R = getIntList()
        intX = A[p[L][0]][p[L][1]]
        while intX is not R:
            x = p[intX][0]
            y = p[intX][1]
            d.dmp((intX, x, y, mp), 'intX, x, y, mp')
            intX += D
            nx = p[intX][0]
            ny = p[intX][1]
            mp +=  abs(x-nx) + abs(y-ny)
            d.dmp((intX, nx, ny, mp), 'intX, nx, ny, mp')
        d.dmp((L, R, mp), 'L, R, mp')
        print(mp)
    return None


ans = prob()
if ans is None:
    pass
elif type(ans) == list and ans[0] == 'col':
    for elm in ans[1]:
        print(elm)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
h, w, d = map(int, input().split())
p = dict()
for i in range(h):
    for j, x in enumerate(map(int, input().split())):
        p[x] = (i, j)

dist = [[None]*(h*w) for _ in p.keys()]

def func(a, b):

    if a == b:
        dist[a][b] = 0
        return 0
    else:
        if dist[a][b]:
            return dist[a][b]
        else:
            x, y = p[b]
            s, t = p[b-d]
            dist[b-d][d] = abs(x-s)+abs(y-t)
            return func(a, b-d) + dist[b-d][d]


q = int(input())
for i in range(q):
    a, b = map(int, input().split())
    ans = func(a, b)
    print(ans)

Submission status: Runtime Error

Solution code:
import heapq
import sys
input=sys.stdin.readline
from collections import defaultdict
h, w, d = map(int, input().split())
p = dict()
D = defaultdict(list)
for i in range(h):
    for j, x in enumerate(map(int, input().split())):
        p[x] = (x, i, j)
        heapq.heappush(D[x%d], (x, i, j))

q = int(input())
for i in range(q):
    a, b = map(int, input().split())
    v = D[a%d]
    ans = 0
    for x, i, j in v:
        if x == a:
            s, t = i, j
        elif a < x <= b:
            ans += abs(s-i)+abs(t-j)
            s, t = i, j
            if x == b:
                break
    print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
H, W, D = map(int, input().split())
A = [None] * (H * W + 1)
for h in range(H):
    for w, a in enumerate(input().split()):
        A[int(a)] = (h + 1, w + 1)
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]
M = {}
def skill(a, b):
    if a == b:
        return 0
    if (a, b) in M:
        return M[(a, b)]
    left = abs(A[a][0] - A[a + D][0]) + abs(A[a][1] - A[a + D][1])
    center = skill(a + D, b - D)
    right = abs(A[b - D][0] - A[b][0]) + abs(A[b - D][1] - A[b][1])
    M[(a, b)] = left + center + right
    return M[(a, b)]
for l, r in LR:
    print(skill(l, r))

Submission status: Runtime Error

Solution code:
H, W, D = map(int, input().split())
A = [None] * (H * W + 1)
for h in range(H):
    for w, a in enumerate(input().split()):
        A[int(a)] = (h + 1, w + 1)
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]
M = {}
def skill(a, b):
    if a == b:
        return 0
    if (a, b) in M:
        return M[(a, b)]
    left = abs(A[a][0] - A[a + D][0]) + abs(A[a][1] - A[a + D][1])
    center = skill(a + D, b - D)
    right = abs(A[b - D][0] - A[b][0]) + abs(A[b - D][1] - A[b][1])
    M[(a, b)] = left + center + right
    return M[(a, b)]
for l, r in LR:
    print(skill(l, r))

Submission status: Runtime Error

Solution code:
h,w,d = map(int,input().split())
hw = {}
for i in range(h):
        check = list(map(int,input().split()))
        for j in range(w):
                hw[check[j]] = [i+1,j+1]
q = int(input())
for i in range(q):
        l,r = map(int,input().split())
        x,y = hw[l][0],hw[l][1]
        check = 0
        while True:
                if l == r:print(check);break
                l = (d + l)%(h*w)
                check += abs(hw[l][0]-x) + abs(hw[l][1]-y)
                x,y = hw[l][0],hw[l][1]

Submission status: Runtime Error

Solution code:
# use faster method than input()
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def manhattan(pos1, pos2):
    return abs(pos1[0]-pos2[0]) + abs(pos2[1]-pos1[1])


H, W, D = map(int, input().split())
A = [(0, 0)]*(H*W)
for r in range(H):
    l = list(map(int, input().split()))
    for c in range(W):
        A[l[c]-1] = (r, c)

dist = [0]*(H*W)
for i in range(D, H*W):
    dist[i] = dist[i-D]+manhattan(A[i], A[i+D])


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

ans_list = [0]*Q
for i in range(Q):
    ans = 0
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    ans = dist[b]-dist[a]
    ans_list[i] = ans

for ans in ans_list:
    print(ans)

Submission status: Runtime Error

Solution code:
h,w,d = map(int,input().split())
hw = [[0,0] for _ in range(h*w+1)]
for i in range(h):
    row = list(map(int,input().split()))
    for j in range(w):
        hw[row[j]] = [i,j]

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

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

Submission status: Runtime Error

Solution code:
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
pos = [None]*(H*W+1)
for i, elem in enumerate(A):
    for j, a in enumerate(elem):
        pos[a] = (i, j)
acc = [[] for _ in range(D+1)]
for i in range(1, D+1):
    tmp = i
    s = 0
    acc[i].append(s)
    while tmp <= H*W-D:
        s += abs(pos[tmp][0]-pos[tmp+D][0])+abs(pos[tmp][1]-pos[tmp+D][1])
        acc[i].append(s)
        tmp += D

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

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(500 * 500)

ANS = dict()


def f(l, r):
    if (l, r) in ANS:
        return ANS[(l, r)]
    if l == r:
        return 0
    ans = f(l + D, r) + abs(P[l][0] - P[l + D][0]) + abs(P[l][1] - P[l + D][1])
    ANS[(l, r)] = ans
    return ans


H, W, D = [int(x) for x in input().split()]
P = [0] * (H * W + 1)
for h in range(H):
    A = [int(x) for x in input().split()]
    for w, a in enumerate(A):
        P[a] = (h, w)

Q = int(input())

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

for i in range(Q):
    print(f(L[l], R[r]))

Submission status: Runtime Error

Solution code:
ANS = dict()


def f(l, r):
    if (l, r) in ANS:
        return ANS[(l, r)]
    if l == r:
        return 0
    return f(l + D, r) + abs(P[l][0] - P[l + D][0]) + abs(P[l][1] - P[l + D][1])


H, W, D = [int(x) for x in input().split()]
P = [0] * (H * W + 1)
for h in range(H):
    A = [int(x) for x in input().split()]
    for w, a in enumerate(A):
        P[a] = (h, w)

Q = int(input())

for q in range(Q):
    l, r = [int(x) for x in input().split()]
    print(f(l, r))

Submission status: Runtime Error

Solution code:
# coding:utf-8

import sys

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


def inpl(): return list(map(int, input().split()))


H, W, D = inpl()

num_coordinate = {}
for i in range(H):
    w = inpl()
    for j in range(W):
        num_coordinate[w[j]] = (i, j)

c_sum = {}
for d in range(1, D + 1):
    c_sum[d] = [0]

for d in range(1, D + 1):
    for n in range(d + D, H * W, D):
        c_sum[d].append(c_sum[d][-1] + abs(num_coordinate[n][0] - num_coordinate[n - D][0])
                        + abs(num_coordinate[n][1] - num_coordinate[n - D][1]))

Q = int(input())
for _ in range(Q):
    l, r = inpl()
    index = (l - 1) % D + 1
    index_l, index_r = (l - 1) // D, (r - 1) // D

    print(c_sum[index][index_r] - c_sum[index][index_l])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
h,w,d = map(int, input().split())
dd = {}
field = []
for hi in range(h):
    line = list(map(int, input().split()))
    field.append(line)
    for wi in range(w):
        dd[line[wi]] = (hi, wi)
q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]

memo = [[-1 for _ in range(h*w)] for _ in range(h*w)]
def calc(s,r):
    if s==r:
        return 0
    elif memo[s][r]>0:
        return memo[s][r]

    h1,w1 = dd[s]
    s2 = field[h1][w1]+d
    h2,w2 = dd[s2]
    res = abs(h1-h2) + abs(w1-w2) + calc(s2, r)
    memo[s][r] = res
    return res

for (l,r) in lr:
    print(calc(l,r))

Submission status: Runtime Error

Solution code:
h,w,d = map(int, input().split())
vals = {}
for hh in range(1, h+1):
  for ww, v in enumerate(map(int, input().split())):
    ww = ww + 1
    vals[v] = (hh,ww)

costs = {}
def get_cost(l,r):
  global costs
  global vals
  if (l,r) in costs:
    return costs[(l,r)]
  if l == r:
    costs[(l,r)] = 0
    return 0
  cur = vals[l]
  nxt = vals[l+d]
  delta = abs(nxt[0]-cur[0]) + abs(nxt[1]-cur[1])
  costs[(l,r)] = get_cost(l+d,r) + delta
  return costs[(l,r)]

for qq in range(int(input())):
  l, r = map(int, input().split())
  cost = get_cost(l,r)
  print(cost)

Submission status: Runtime Error

Solution code:
H,W,D=map(int,input().split())
A=[[0,0]]*(H*W)
j=0
for i in range(H):
  for a in input().split():
    A[int(a)-1]=[i,j]
    j+=1
  j=0
Q=int(input())
S=[[0]*((H*W-1-i)//D+1) for i in range(D)]
for i in range(D):
  for k in range((H*W-1-i)//D):
    x1=A[D*k+i-1][0]
    x2=A[D*(k+1)+i-1][0]
    y1=A[D*k+i-1][1]
    y2=A[D*(k+1)+i-1][1]
    S[i][k+1]+=S[i][k]+abs(x1-x2)+abs(y1-y2)
ans=0
for q in range(Q):
  l,r=map(int,input().split())
  m=l%D
  ans=S[m][(r-m)//D]-S[m][(l-m)//D]
  print(ans)
  ans=0

Submission status: Runtime Error

Solution code:
H,W,D=map(int,input().split())
A=[[0,0]]*(H*W)
j=0
for i in range(H):
  for a in input().split():
    A[int(a)-1]=[i,j]
    j+=1
  j=0
Q=int(input())
S=[[0]*(((H*W-1)-i)//D+1) for i in range(D)]
for i in range(D):
  for k in range((H*W-1-i)//D):
    x1=A[D*k+i-1][0]
    x2=A[D*(k+1)+i-1][0]
    y1=A[D*k+i-1][1]
    y2=A[D*(k+1)+i-1][1]
    S[i][k+1]+=S[i][k]+abs(x1-x2)+abs(y1-y2)
ans=0
for q in range(Q):
  l,r=map(int,input().split())
  if l!=l%D:
    ans=S[l%D][(r-l%D)//D]-S[l%D][(l-l%D)//D]
  else:
    ans=S[l%D][(r-l%D)//D]
  print(ans)
  ans=0

Submission status: Runtime Error

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

PY = [list(map(int, input().split())) + [i] for i in range(h)]
for i in range(h):#h:高さ
    a.append([int(m) for m in input().split()])

q = int(input())
lr = []
for i in range(q):#h:高さ
    lr.append([int(m) for m in input().split()])

rea = []
for i in range(h * w):
    rea.append([])
for i in range(h):
    for j in range(w):
        rea[i].append([])


for i in range(h):
    for j in range(w):
        rea[w*i+j].append(a[i][j])
        rea[w*i+j].append(i)
        rea[w*i+j].append(j)

rea.sort()

pre = []
for i in range(h*w):
    pre.append([])

for i in range(h):
    for j in range(w):
        lmn = 0
        pre[w * i + j].append(lmn)
        for k in range(i, h*w,d):
            lmn += abs(rea[w*i+j + k][1] - rea[w*i+j+d + k][1]) + abs(rea[w*i+j + k][2]- rea[w*i+j+d + k][2])
            pre[w*i+j].append(lmn)

for i in range(q):
    print(pre[lr[i][0] - 1][(lr[i][1]-lr[i][0])//d - 1])

Submission status: Runtime Error

Solution code:
H,W,D=map(int,input().split())
data=[]
for i in range(1,H+1):
    tmp=list(map(int,input().split()))
    for j in range(1,W+1):
        data.append([i,j,tmp[j-1]])

data.sort(key=lambda x:x[2])

ruiseki=[]
for i in range(D):
    tmp=[0]
    j=i+D
    while(j<H*W):
        tmp.append( abs(data[j][0]-data[j-D][0]) +abs(data[j][1]-data[j-D][1]) +tmp[-1])
        j+=D
    ruiseki.append(tmp)

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

Submission status: Runtime Error

Solution code:
def inpl(): return [int(i) for i in input().split()]

H, W, D = inpl()
S = dict([])
for i in range(H):
    a = inpl()
    for j in range(W):
        S[a[j]] = [i,j]

dist = [[0] for i in range(D+1) ]
for i in range(1,D+1):
    for j in range(1,-(-(H*W-i)//D)):
        dist[i].append(dist[i][-1] +\
        (abs(S[i+j*D][0]-S[i+(j-1)*D][0])+abs(S[i+j*D][1]-S[i+(j-1)*D][1])))
Q = int(input())
ans = []
for i in range(Q):
    l, r = inpl()
    mod = l % D
    if mod == 0 : mod = D
    l, r = (l-mod)//D, (r-mod)//D
    ans.append(dist[mod][r]-dist[mod][l])
for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
h, w, d = map(int, input().split())
x = []
z = [[0, 0] for i in range(h * w)]
for i in range(h):
    x.append(list(map(int, input().split())))
    for j in range(w):
        z[x[i][j] - 1] = [i + 1, j + 1]
print(z)
s = [0 for _ in range(d)]
for i in range(d):
    a = z[max(0, i - 1)]
    b = z[d + i - 1]
    s[i] = [abs(a[0] - b[0]) + abs(a[1] - b[1])]
    j = 1
    while(True):
        if d * (j + 1) + i <= h * w:
            a = z[d * j + i - 1]
            b = z[d * (j + 1) + i - 1]
            s[i].append(s[i][-1] + abs(a[0] - b[0]) + abs(a[1] - b[1]))
            j += 1
        else:
            break

Q = int(input())
ans = [0 for _ in range(Q)]
for i in range(Q):
    L, R = map(int, input().split())
    if L == R:
        ans[i] = 0
    elif L // d - 1 < 0:
        ans[i] = s[R % d][R // d - 1]
    else:
        ans[i] = s[R % d][R // d - 1] - s[L % d][L // d - 1]
for i in range(Q):
    print(ans[i])

Submission status: Runtime Error

Solution code:
h, w, d = map(int, input().split())
x = []
z = [None for i in range(h * w)]
for i in range(h):
    x.append(list(map(int, input().split())))
    for j in range(w):
        z[x[i][j] - 1] = [i + 1, j + 1]

s = [None for _ in range(d)]
for i in range(d):
    a = z[max(0, i - 1)]
    b = z[d + i - 1]
    s[i] = [abs(a[0] - b[0]) + abs(a[1] - b[1])]
    j = 1
    while(True):
        if d * (j + 1) + i <= h * w:
            a = z[d * j + i - 1]
            b = z[d * (j + 1) + i - 1]
            s[i].append(s[i][-1] + abs(a[0] - b[0]) + abs(a[1] - b[1]))
            j += 1
        else:
            break

Q = int(input())
ans = [None for _ in range(Q)]
for i in range(Q):
    L, R = map(int, input().split())
    if L == R:
        ans[i] = 0
    elif L // d - 1 < 0:
        ans[i] = s[R % d][R // d - 1]
    else:
        ans[i] = s[R % d][R // d - 1] - s[L % d][L // d - 1]
for i in range(Q):
    print(ans[i])

Submission status: Runtime Error

Solution code:
h, w, d = map(int, input().split())
x = []
z = [None for i in range(h * w)]
for i in range(h):
    x.append(list(map(int, input().split())))
    for j in range(w):
        z[x[i][j] - 1] = [i + 1, j + 1]

s = [None for _ in range(d)]
for i in range(d):
    a = z[i - 1]
    b = z[d + i - 1]
    s[i] = [abs(a[0] - b[0]) + abs(a[1] - b[1])]
    j = 1
    while(True):
        if d * (j + 1) + i <= h * w:
            a = z[d * j + i - 1]
            b = z[d * (j + 1) + i - 1]
            s[i].append(s[i][-1] + abs(a[0] - b[0]) + abs(a[1] - b[1]))
            j += 1
        else:
            break

Q = int(input())
ans = [None for _ in range(Q)]
for i in range(Q):
    L, R = map(int, input().split())
    if L == R:
        ans[i] = 0
    elif L // d - 1 < 0:
        ans[i] = s[R % d][R // d - 1]
    else:
        ans[i] = s[R % d][R // d - 1] - s[L % d][L // d - 1]
for i in range(Q):
    print(ans[i])

Submission status: Runtime Error

Solution code:
I=lambda:[int(i) for i in input().split()]
h,w,d=I()
p=[[-1,-1] for i in range(h*w+1) ]
a=[]
for i in range(h):
  a.append(I())
  for j in range(w):
    p[a[i][j]]=[i,j]

import sys
sys.setrecursionlimit(100000)
from functools import lru_cache

@lru_cache(maxsize=100000)
def dist_d(s,g,d):
  if s==g:
    return 0
  else:
    y0,x0=p[s]
    s = a[y0][x0]+d
    y,x = p[s]
    return abs(x-x0)+abs(y-y0) + dist_d(s,g,d)
  
for i in range(int(input())):
  s,g=I()
  print(dist_d(s,g,d))

Submission status: Runtime Error

Solution code:
import numpy as np
H,W,D = map(int,input().split())
a = [input().split() for l in range(H)]
Q = int(input())
b = [input().split() for l in range(Q)]
a = np.array(a)
b = np.array(b)
a = np.int64(a)
b = np.int64(b)
ans = []
memo = [[-1]*302 for i in range(302)]
for i in range(Q):
  syo = b[i,0]
  go = b[i,1]
  if memo[syo][go] != -1:
    ans.append(memo[syo][go])
    continue
  syouhi = 0
  while syo != go:
    c = np.where(a == syo)
    syo += D
    d = np.where(a == syo)
    syouhi += abs(c[0][0] - d[0][0]) + abs(c[1][0] - d[1][0])
  ans.append(syouhi)
  memo[syo][go] = syouhi
for i in range(Q):
  print(ans[i])

Submission status: Runtime Error

Solution code:
H,W,D=list(map(int,input().split()))
arr=[0 for i in range(H*W+1)]
for y in range(H):
    for x,n in enumerate(map(int,input().split())):
        arr[n]=[x,y]

dic={}

Q=int(input())
for i in range(Q):
    ans=0
    now,goal= list(map(int,input().split()))
    nx=arr[now][0]
    ny=arr[now][1]
    tmp=now
    for j in range((goal-now)//D):
        if dic.get(tmp*H*W+goal,0)!=0:
            dic[now*H*W+goal]=ans+dic[tmp*H*W+goal]
            break
        tmp+=D
        x=arr[tmp][0]
        y=arr[tmp][1]
        ans+=abs(x-nx)+abs(y-ny)
        nx=x
        ny=y
        dic[now*H*W+tmp]=ans
    print(dic[now*H*W+goal])

Submission status: Runtime Error

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

field = []

for i in range(h):
	field.append(map(int,raw_input().split()))

n = int(input())

arr = [[] for i in range(901)]

inputs = []

for i in range(n):
	inputs.append(map(int,raw_input().split()))


for i in range(h):
	for j in range(w):
		arr[field[i][j]] = [i+1,j+1]


for i in range(n):
	l,r = inputs[i]

	ans = 0

	t = 1
	while l + d * t <= r:
		ans += abs(arr[l+d*t][0] - arr[l+d*(t-1)][0]) + abs(arr[l+d*t][1] - arr[l+d*(t-1)][1])
		t += 1

	print ans

Submission status: Runtime Error

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

field = []

for i in range(h):
	field.append(map(int,raw_input().split()))

n = int(input())

arr = [[] for i in range(901)]

for i in range(h):
	for j in range(w):
		arr[field[i][j]] = [i+1,j+1]

for i in range(n):
	l,r = map(int,raw_input().split())

	ans = 0

	t = 1
	while l + d * t <= r:
		ans += abs(arr[l+d*t][0] - arr[l+d*(t-1)][0]) + abs(arr[l+d*t][1] - arr[l+d*(t-1)][1])
		t += 1

	print ans

Submission status: Runtime Error

Solution code:
H, W, D=map(int, input().split())
pos={}
for i in range(H):
    A=list(map(int, input().split()))
    for j in range(W):
        pos[A[j]]=(i, j)
p=[0]*(H*W)
for i in range(D+1,H*W):
    p[i]=p[i-D]+abs(pos[i][0]-pos[i-D][0])+abs(pos[i][1]-pos[i-D][1])
Q=int(input())
for _ in range(Q):
    L, R=map(int, input().split())
    print(p[R]-p[L])

Submission status: Runtime Error

Solution code:
H, W, D=map(int, input().split())
pos={}
for i in range(H):
    A=list(map(int, input().split()))
    for j in range(W):
        pos[A[j]]=(i, j)
p=[0]*(H*W)
for i in range(D+1,H*W+1):
    p[i]=p[i-D]+abs(pos[i][0]-pos[i-D][0])+abs(pos[i][1]-pos[i-D][1])
Q=int(input())
for _ in range(Q):
    L, R=map(int, input().split())
    print(p[R]-p[L])

Submission status: Runtime Error

Solution code:
H, W, D=map(int, input().split())
pos={}
for i in range(H):
    A=list(map(int, input().split()))
    for j in range(W):
        pos[A[j]]=(i, j)
Q=int(input())
p=[0]*(H*W)
for i in range(D+1,H*W):
    p[i]=p[i-D]+abs(pos[i][0]-pos[i-D][0])+abs(pos[i][1]-pos[i-D][1])
for i in range(Q):
    L, R=map(int, input().split())
    print(p[R]-p[L])

Submission status: Runtime Error

Solution code:
H, W, D=map(int, input().split())
pos={}
for i in range(H):
    A=list(map(int, input().split()))
    for j in range(W):
        pos[A[j]]=(i, j)
Q=int(input())
p=[0 for _ in range(H*W)]
for i in range(D+1,H*W):
    p[i]=p[i-D]+abs(pos[i][0]-pos[i-D][0])+abs(pos[i][1]-pos[i-D][1])
for i in range(Q):
    L, R=map(int, input().split())
    print(p[R]-p[L])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations

sys.setrecursionlimit(10000)


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


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap



@mt
def slv(H, W, D, A, Q, LR):
    A_ = {}
    for i, r in enumerate(A):
        for j, c in enumerate(r):
            A_[c] = (i, j)
    
    @lru_cache(maxsize=None)
    def f(l, r):
        if l == r:
            return 0
        ans = 0
        i, j = A_[l]
        x, y = A_[l+D]
        l += D
        ans += abs(x-i)
        ans += abs(y-j)
        ans += f(l, r)
        return ans
    
    for l, r in LR:
        print(f(l, r))
    



def main():
    H, W, D = read_int_n()
    A = [read_int_n() for _ in range(H)]
    Q = read_int()
    LR = [read_int_n() for _ in range(Q)]
    slv(H, W, D, A, Q, LR)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

data = {A[i][j]:j + i * W for i in range(H) for j in range(W)}
move = [0] * (H*W + 1)

for i in range(1+D,H*W+1):
    a,b = data[i],data[i-D]
    move[i] = abs(a%W - b % W) + abs(a//W - b//W)

memo = [[None] * (H*W) for _ in range(H*W)]
for l,r in LR:
    if l == r:
        print(0)
        continue
    if memo[l][r]:
        print(memo[l][r])
    else:
        t = sum(move[l+D:r+1:D])
        memo[l][r] = t
        print(t)

Submission status: Runtime Error

Solution code:
H,W,D = map(int,input().split())
d = {}
for i in range(H):
    A = list(map(int,input().split()))
    for j in range(W):
        d[A[j]] = (i,j)
m = []
for i in range(1,D+1):
    mm = [0]
    for j in range(i+D,H*W,D):
        k = (j-i)//D
        dd = mm[k-1]+abs(d[j][0]-d[j-D][0])+abs(d[j][1]-d[j-D][1])
        mm.append(dd)
    m.append(mm)
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    if L%D != 0:
        mm = m[L%D-1]
        Lq = L//D
        Rq = R//D
        print(mm[Rq]-mm[Lq])
    else:
        mm = m[D-1]
        Lq = L//D
        Rq = R//D
        print(mm[Rq-1]-mm[Lq-1])

Submission status: Runtime Error

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

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


def consumption(point_A, point_B):
    return abs(point_A[0] - point_B[0]) + abs(point_A[1] - point_B[1])


X = []
for i in [D] + list(range(1, D)):
    power = 0
    x = [0]
    for j in range(int((H * W - i) / D)):
        power += consumption(A[i - 1 + j * D], A[i - 1 + (j + 1) * D])
        x.append(power)
        #print("{}->{}".format(A[i - 1], A[i - 1 + (j + 1) * D]))
    X.append(x)
# print(X)
for i in range(Q):
    l = int(L[i] / D)
    r = int(R[i] / D)
    #print(X[L[i] % D], l, r)
    print(X[L[i] % D][r] - X[L[i] % D][l])