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:
H, W, D = map(int, input().split(" "))
grid = list()
d = dict()
for y in range(H):
    line = list(map(int, input().split(" ")))
    for x in range(W):
        num = line[x]
        d[num] = (x, y)

memo = dict()


def get_cost(num):
    if num <= D:
        return 0
    if num in memo:
        return memo[num]
    pos_x, pos_y = d[num]
    pos_x_1, pos_y_1 = d[num-D]
    cost = get_cost(num-D) + abs(pos_x - pos_x_1) + abs(pos_y - pos_y_1)
    memo[num] = cost
    return cost


Q = int(input())
exams = list()
for _ in range(Q):
    exams.append([int(i) for i in input().split(" ")])

for exam in exams:
    l, r = exam
    print(get_cost(r) - get_cost(l))

Submission status: Runtime Error

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    H,W=MI()
    A=LLIN(H)
    odds=[]
    ans=[]
    for i in range(H):
        if i&1:
            for j in range(W)[::-1]:
                if A[i][j]&1:
                    if j==0:
                        dy=1
                        dx=0
                    else:
                        dy=0
                        dx=-1
                    if i+dy!=H:
                        
                        ans.append((i+1,j+1,i+dy+1,j+dx+1))
                        A[i+dy][j+dx]+=1
        else:
            for j in range(W):
                if A[i][j]&1:
                    if j==W-1:
                        dy=1
                        dx=0
                    else:
                        dy=0
                        dx=1
                    if i+dy!=H:
                       
                        ans.append((i+1,j+1,i+dy+1,j+dx+1))
                        A[i+dy][j+dx]+=1

    print(len(ans))
    for a in ans:
        print(*a)
    


if __name__ == '__main__':

Submission status: Runtime Error

Solution code:
#89d
from functools import lru_cache

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

value_coordinate_dict = {}

for i in range(1,H+1):
    A_list = [str(e) for e in input().split()]
    for j in range(1,W+1):
        value_coordinate_dict[int(A_list[j-1])] = (i,j) 

@lru_cache(maxsize=1000)
def calc_cmp(from_number,to_number): #cmp:消費comsumption 魔力magic power
    #print("###",from_number,"→",to_number)

    #終了条件
    if from_number == to_number:
        #print(from_number,"→",to_number,"= 0")
        return 0
    elif from_number + D == to_number:
        from_coordinate = value_coordinate_dict[from_number]
        to_coordinate = value_coordinate_dict[to_number]
        cmp = abs(to_coordinate[0] - from_coordinate[0]) + abs(to_coordinate[1] - from_coordinate[1])
        #print(from_number,"→",to_number,"=",cmp)
        return cmp
    #継続
    else:
        next_number = from_number + D
        return calc_cmp(next_number,to_number) + calc_cmp(from_number,next_number)        
            
Q = int(input())

for i in range(Q):
    L,R = map(int, input().split())
    print(calc_cmp(L,R))

Submission status: Runtime Error

Solution code:
H,W,D=map(int,input().split())
import collections
table=collections.defaultdict(tuple)

field=[list(map(int,input().split())) for i in range(W)]
for i in range(H):
  for j in range(W):
    table[field[i][j]]=(i,j)
Q=int(input())
LR=[list(map(int,input().split())) for i in range(Q)]

for i in range(Q):
  ans=0
  x = table[LR[i][0]]
  value=LR[i][0]
  now=list(x)
  while(value != LR[i][1]):
    value+=D
    next=table[value]
    ans+=abs(next[0]-now[0])+abs(next[1]-now[1])
    now[0],now[1]=next[0],next[1]
    
  print(ans)

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

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)] 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 // D] - cost[(l - 1) % D][l // D])

Submission status: Runtime Error

Solution code:
# D
import numpy as np
h, w, d = map(int, input().split())
field = []
for _ in range(h):
    wi = list(map(int, input().split()))
    field.append(wi)
field = np.array(field)

def search(field, l, r, d):
    mana = 0
    while l < r:
        mae = np.where(field==l)
        i, j = mae[0][0], mae[1][0]
        ushiro = np.where(field==l+d)
        x, y = ushiro[0][0], ushiro[1][0]
        mana += abs(x-i) + abs(y-j)
        
        l += d
    print(mana)

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    search(field=field, l=l, r=r, d=d)

Submission status: Runtime Error

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+5)//d)] for _ in range(h*w+5)]

for i in range(h*w-d+3):
    for j in range(1,(h*w+5)//d):
        if i+d*j <= h*w+3:
            dfromd[i][j] = dfromd[i][j-1] + abs(dx[i+d*j]-dx[i+d*(j-1)])+abs(dy[i+d*j]-dy[i+d*(j-1)])

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

Submission status: Runtime Error

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

dic = {}


def magic_test(L, R, power):
    if L == R:
        return power
    x, y = dic[L]
    nx, ny = dic[L+D]
    power += abs(x-nx) + abs(y-ny)
    return magic_test(L+D, R, power)


for y in range(1, H+1):
    A = list(map(int, input().split()))

    for x, a in enumerate(A, 1):
        dic[a] = [x, y]

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    ans = magic_test(L, R, 0)
    print(ans)

Submission status: Runtime Error

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]] = 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+1)
for _ in range(int(input())):
  l, r = map(int, input().split())
  print(memo[a[r]] - memo[a[l]])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
h, w, d = map(int, input().split())
a = {}
l = list(range(h * w))
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]) = 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: Runtime Error

Solution code:
h,w,d,*l=map(int,open(0).read().split())
s=h*w+1;x=[0]*s;y=[0]*s;k=[0]*s
for i,a in enumerate(l[:s]):x[a]=i//w;y[a]=i%w
for i in range(d+1,s-1):k[i]=k[i-d]+abs(x[i]-x[i-d])+abs(y[i]-y[i-d])
for l,r in zip(l[s::2],l[s+1::2]):print(k[r]-k[l])

Submission status: Runtime Error

Solution code:
from functools import lru_cache

def main():
    @lru_cache(maxsize=1000)
    def dfs(d,R,sx,sy):
        if d == R:
            return 0
        x = 0
        y = 0
        for i in range(H):
            for j in range(W):
                if A[i][j] == d + D:
                    x = i
                    y = j
                    break
            else:
                continue
            break
        
        res = abs(x - sx) + abs(y - sy) + dfs(d+D,R,x,y)

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

    for _ in range(Q):
        L, R = map(int, input().split())
        sx = 0
        sy = 0
        for i in range(H):
            for j in range(W):
                if A[i][j] == L:
                    sx = i
                    sy = j
                    break
            else:
                continue
            break
        print(dfs(L,R,sx,sy))

        
        
        

main()

Submission status: Runtime Error

Solution code:
def main():
    def dfs(d,R,sx,sy):
        if d == R:
            return 0
        x = 0
        y = 0
        for i in range(H):
            for j in range(W):
                if A[i][j] == d + D:
                    x = i
                    y = j
                    break
            else:
                continue
            break
        
        res = abs(x - sx) + abs(y - sy) + dfs(d+D,R,x,y)

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

    for _ in range(Q):
        L, R = map(int, input().split())
        sx = 0
        sy = 0
        for i in range(H):
            for j in range(W):
                if A[i][j] == L:
                    sx = i
                    sy = j
                    break
            else:
                continue
            break
        print(dfs(L,R,sx,sy))

        
        
        

main()

Submission status: Runtime Error

Solution code:
H,W,D=map(int,input().split());S=H*W;A=[map(int,input().split())for _ in range(H)];Q,*L=open(0);d=[0]*S;e=[0]*S
for i,l in enumerate(A):
 for j,v in enumerate(l):d[v-1]=(i,j)
for i in range(S):
 if i>=D:e[i]=sum(abs(p-q)for p,q in zip(d[i-D],d[i]))+e[i-D]
for i in L:l,r=map(int,i.split());print(e[r-1]-e[l-1])

Submission status: Runtime Error

Solution code:
H,W,D = map(int, input().split())
fields = []
amaris = [[0] * (H*W)//D+1 for i in range(D)] # あまり
for i in range(H):
    row = list(map(int, input().split()))
    # あまりがいくつかで分類
    for j,e in enumerate(row):
        n = (e-1) // D
        m = (e-1) % D
        amaris[m][n] = (i,j)

# print(amaris[:10])
# あまりごとに累積和を取っておく
acc = [[0] * (H*W)//D+1 for i in range(D)]
for i in range(D):
    cnt = 0
    x_pre, y_pre = amaris[i][0]
    for j in range(1,(H*W)//D+1):
        coords = amaris[i][j]
        if isinstance(coords,int): break
        x = coords[0]
        y = coords[1]
        cnt += abs(x-x_pre)+abs(y-y_pre)
        acc[i][j] = cnt
        x_pre = x
        y_pre = y

# print(acc)

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

Submission status: Runtime Error

Solution code:
H,W,D = map(int, input().split())
fields = []
amaris = [[0] * (H*W) for i in range(D)] # あまり
for i in range(H):
    row = list(map(int, input().split()))
    # あまりがいくつかで分類
    for j,e in enumerate(row):
        n = (e-1) // D
        m = (e-1) % D
        amaris[m][n] = (i,j)

# print(amaris[:10])
# あまりごとに累積和を取っておく
acc = [[0] * (H*W) for i in range(D)]
for i in range(D):
    cnt = 0
    x_pre, y_pre = amaris[i][0]
    for j in range(1,(H*W)//D+1):
        coords = amaris[i][j]
        if isinstance(coords,int): break
        x = coords[0]
        y = coords[1]
        cnt += abs(x-x_pre)+abs(y-y_pre)
        acc[i][j] = cnt
        x_pre = x
        y_pre = y


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

Submission status: Runtime Error

Solution code:
h, w, d = map(int, input().split())
numlist = []
for i in range(h * w):
  numlist.append([])

for i in range(h):
  a = list(map(int, input().split()))
  for j in range(w):
    numlist[a[j]-1].append(i + 1)
    numlist[a[j]-1].append(j + 1)
    
dlist = []
for i in range(d):
  delem = []
  su = 0
  for j in range(i, h*w-d, d):
    su += abs(numlist[j-1][0] - numlist[j+d-1][0]) + abs(numlist[j-1][1] - numlist[j+d-1][1])
    delem.append(su)
  dlist.append(delem)
  
q = int(input())

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

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int H, W, D;
    cin >> H >> W >> D;
    vector<vector<int> > A(H, vector<int>(W, 0));
    for (auto &a : A) for (auto &_a : a) cin >> _a;
    vector<pair<int, int> > C(H*W);
    for (int i = 0; i<H; i++) {
        for (int j = 0; j<W; j++) {
            C[A[i][j]-1] = make_pair(i, j);
        }
    }
    int Q;
    cin >> Q;
    vector<pair<int, int> > LR(Q);
    for (auto &lr : LR) cin >> lr.first >> lr.second;
    for (auto lr : LR) {
        int cost = 0;
        int l = lr.first-1;
        while (l < lr.second-1) {
            cost += abs(C[l].first-C[l+D].first) + abs(C[l].second-C[l+D].second);
            l += D;
        }
        printf("%d\n", cost);
    }
    return 0;
}

Submission status: Runtime Error

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

a = [[0 for _ in range(w)] for _ in range(h)]
masu = {}
for i in range(h):
    a[i] = list(map(int, input().split())
    for j in range(w):
        masu[a[i][j]] = (i,j)
"""
masu = {}
for i in range(h):
    for j in range(w):
        masu[a[i][j]] = (i,j)
"""
point = [0] * (h*w)
for i in range(1,h*w-d+1):
    point[i] = abs(masu[i][0] - masu[i+d][0]) + abs(masu[i][1] - masu[i+d][1])


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

Submission status: Runtime Error

Solution code:
def solve(row, col, d):
    x_map = [0]*(row**2)

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

#    for k in range(row):
#        print(x_map[k*row:(k+1)*row])
#
    q = int(input())

    mp = 0
    for _ in range(q):
        l, r = map(int, input().split())
        for current_pos in range(l+d-1, r, d):
#            print("curre_pos : {0}".format(current_pos))
#            print("cp : {0}".format(x_map[current_pos]))
#            print("pp : {0}".format(x_map[current_pos-d]))
            cp = x_map[current_pos]
            pp = x_map[current_pos-d]
            mp += abs(cp[1] - pp[1]) + abs(cp[0] - pp[0])
        print(mp)
        mp = 0


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

Submission status: Runtime Error

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

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

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

table = [0] * (H*W)
for i in range(D+1, H*W):
    x, y = a[i]
    x_, y_ = a[i-D]
    table[i] = table[i-D] + abs(x - x_) + abs(y - y_)

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

Submission status: Runtime Error

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

a = [None] * (H*W+1)

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

table = [0] * (H*W)
for i in range(D+1, H*W):
    x, y = a[i]
    x_, y_ = a[i-D]
    table[i] = table[i-D] + abs(x - x_) + abs(y - y_)

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

Submission status: Runtime Error

Solution code:
import numpy as np
h,w,d=map(int,input().split())
a=[int(i) for i in input().split()]
for i in range(h-1):
    a=np.vstack((a,[int(i) for i in input().split()]))
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i] = map(int,input().split())
for i in range(q):
    ans=0
    for j in range((r[i]-l[i])//d):
        ans+=np.abs(np.where(a==l[i]+j*d)[0][0] - np.where(a==l[i]+d+j*d)[0][0])
        ans+=np.abs(np.where(a==l[i]+j*d)[1][0] - np.where(a==l[i]+d+j*d)[1][0])
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
h,w,d=map(int,input().split())
a=[int(i) for i in input().split()]
for i in range(h-1):
    a=np.vstack((a,[int(i) for i in input().split()]))
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i] = map(int,input().split())
 
for i in range(q):
    ans=0
    for j in range((r[i]-l[i])//d):
        ans+=np.abs(np.where(a==l[i]+j*d)[0][0] - np.where(a==l[i]+d+j*d)[0][0])
        ans+=np.abs(np.where(a==l[i]+j*d)[1][0] - np.where(a==l[i]+d+j*d)[1][0])
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
h,w,d=map(int,input().split())
a=[int(i) for i in input().split()]
for i in range(h-1):
    a=np.vstack((a,[int(i) for i in input().split()]))
q=int(input())
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i] = map(int,input().split())

for i in range(q):
    ans=0
    for j in range((r[i]-l[i])//d):
        ans+=np.abs(np.where(a==l[i]+j*d)[0][0] - np.where(a==l[i]+d+j*d)[0][0])
        ans+=np.abs(np.where(a==l[i]+j*d)[1][0] - np.where(a==l[i]+d+j*d)[1][0])
    print(ans)

Submission status: Runtime Error

Solution code:
def main():
	H, W, D = map(int,input().split())
	pos = [0]*(H*W+1)
	for i in range(H):
		A = list(map(int, input().split()))
		for j in range(W):
			pos[A[j]] = [i, j]
	Q = int(input())
	lr = [0]*Q
	for i in range(Q):
		lr[i] = list(map(int, input().split()))
	ans = dict()
	for i in range(1, H*W+1-D):
		pre = i
		cur = i
		d = 0
		while cur < H*W+1:
			pre_pos = pos[pre]
			cur_pos = pos[cur]
			d += abs(pre_pos[0]-cur_pos[0])+abs(pre_pos[1]-cur_pos[1])
			ans[(i, cur)] = d
			pre = cur
			cur += D
	for i in range(Q):
		print(ans[(lr[i][0], lr[i][1])])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
INF = float('inf')
H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]

d = defaultdict(lambda:[])

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

cost = defaultdict(lambda:[])
for r in range(1,D+1):
    for m in range(0,H*W//D):
        if D*(m+1)+r <= H*W:
            cost[r].append(abs(d[D*m+r][0]-d[D*(m+1)+r][0])+abs(d[D*m+r][1]-d[D*(m+1)+r][1]))
for r in range(1,D+1):
    for m in range(len(cost[r])-1):
        cost[r][m+1] += cost[r][m]

Q = int(input())

def magic(L,R):
    r = L%D
    if r == 0:
        r = D
    ml = (L-r)//D
    mr = (R-r)//D
    res = cost[r][mr-1]
    if ml != 0:
        res -= cost[r][ml-1]
    return res


for _ in range(Q):
    L,R = map(int,input().split())
    print(magic(L,R))

Submission status: Runtime Error

Solution code:
H, W, D = [int(x) for x in input().split()]
board_dict = {}
for i in range(1, H+1):
    tmp = [int(x) for x in input().split()]
    for j, k in enumerate(tmp):
        board_dict[k] = (i, j+1)
Q = int(input())
lr_list = []
for _ in range(Q):
    lr_list.append([int(x) for x in input().split()])

for l, r in lr_list:
    res = 0
    now = l
    next = now+D
    now_pos = board_dict[now]
    next_pos = board_dict[next]
    while now != r:
        now_pos = board_dict[now]
        next_pos = board_dict[next]
        res += abs(next_pos[0] - now_pos[0]) + abs(next_pos[1] - now_pos[1])
        now = next
        next = now+D
    print(res)

Submission status: Runtime Error

Solution code:
from functools import partial
from itertools import islice


def take(n, iterable):
    return list(islice(iterable, n))


def chunked(iterable, n):
    return iter(partial(take, n, iter(iterable)), [])


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


def solve(s):
    h, w, d, *aqlr = map(int, s.split())
    n = h * w
    pos = [(i // w, i % w) for i, _a in enumerate(aqlr[:n])]
    cost = [0] * (n + 1)
    for i in range(d + 1, n + 1):
        cost[i] = cost[i - d] + distance(pos[i - d], pos[i])
    return "\n".join(["%d" % (cost[r] - cost[l]) for l, r in chunked(aqlr[n + 1:], 2)])


n, m, d = map(int, input().split())
l = '{} {} {}\n'.format(n, m, d) + '\n'.join([input() for _ in range(n)])
q, = map(int, input().split())
l += '\n{}\n'.format(q) + '\n'.join([input() for _ in range(q)])
print(solve(l))

Submission status: Runtime Error

Solution code:
def loc_decide(loc, w, num):
    location = [i for i in range(len(loc)) if loc[i] == num][0]
    row = location // w
    column = location % w
    return [row, column]

h, w, d = map(int, input().split())
loc = []
for _ in range(h):
    tmp = list(map(int, input().split()))
    for i in range(len(tmp)):
        loc.append(tmp[i])
n = int(input())
mem = []
for _ in range(n):
    start, end = map(int, input().split())
    dist = 0
    if start == end:
        print(dist)
        mem.append([start, end, dist])
    else:
        judge = [i for i in range(len(mem)) if mem[i][0]==start and mem[i][1]==end]
        if len(judge) >=1:
            print(mem[judge[0][2]])
        else:
            for i in range(start, end+1, d):
                if i == start:
                    prev_loc = loc_decide(loc, w, i)
                else:
                    next_loc = loc_decide(loc, w, i)
                    dist += (abs(next_loc[0]- prev_loc[0]) + abs(next_loc[1] - prev_loc[1]))
                    prev_loc = next_loc
            mem.append([start, end, dist])
            print(dist)

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

number_dict = {}
for h in range(H):
    for w in range(W):
        number_dict[A[h][w]] = (w+1, h+1)
        
       
for i in range(Q):
    tmp = 0
    now = LR[i][0]
    now_state = number_dict[now]
    
    while True:
        if now == LR[i][1]:
            break
        
        tmp += abs(number_dict[now+D][0] - now_state[0]) + abs(number_dict[now+D][1] - now_state[1])
        now = now + D
        now_state = number_dict[now+D]
        

            
    print(tmp)

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

number_dict = {}
for h in range(H):
    for w in range(W):
        number_dict[A[h][w]] = (w+1, h+1)
        
       
for i in range(Q):
    tmp = 0
    now = LR[i][0]
    
    while True:
        tmp += abs(number_dict[now+D][0] - number_dict[now][0]) + abs(number_dict[now+D][1] - number_dict[now][1])
        now = now + D
        
        if now == LR[i][1]:
            break
            
    print(tmp)

Submission status: Runtime Error

Solution code:
h, w, d = [ int(v) for v in input().split() ]
def manhattan(intuple1,intuple2):
	return abs(intuple1[2]-intuple2[2]) + abs(intuple1[1]-intuple2[1])

grid_list = [ None for i in range(w*h) ]
for i in range(h):
	num_list = [ int(v) for v in input().split() ]
	for j in range(w):
		grid_list[i*h+j] = (num_list[j],i,j)
grid_list = sorted(grid_list)


m = int(input())
for i in range(m):
	l, r = [ int(v) for v in input().split() ]
	score = 0
	left = grid_list[l-1]
	for j in range(l+d,r+d,d):
		right = grid_list[j-1]
		score += manhattan(left,right)
		left = right
	print(score)

Submission status: Runtime Error

Solution code:
h,w,k=map(int,input().split())
pos=[0]*(h*w+1)
for _ in range(h):
  tmp=list(map(int,input().split()))
  for i in range(w):
    pos[tmp[w]]=[i+1,w+1]
print(pos)h,w,k=map(int,input().split())
pos=[0]*(h*w+1)
for i in range(h):
  tmp=list(map(int,input().split()))
  for j in range(w):
    pos[tmp[j]]=[i+1,j+1]
cs=[[0] for _ in range(k+1)]
for i in range(1,k+1):
  for j in range(1,(h*w-i)//k+1):
    x1,y1=pos[i+k*(j-1)][1],pos[i+k*(j-1)][0]
    x2,y2=pos[i+k*j][1],pos[i+k*j][0]
    cs[i].append(abs(y2-y1)+abs(x2-x1)+cs[i][j-1])
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  tmp=l%k
  if tmp==0:
    tmp=k
  l,r=(l-tmp)//k,(r-tmp)//k
  print(cs[tmp][r]-cs[tmp][l])

Submission status: Runtime Error

Solution code:
h,w,d=map(int,input().split())
D=dict()
for i in range(h):
  A=[int(i) for i in input().split()]
  for j in range(w):
    D[A[j]]=[i+1,j+1]
def Dist(x,y):
  return abs(D[x][0]-D[y][0])+abs(D[x][1]-D[y][1])
T=[[0 for _ in range(h*w)] for _ in range(h*w)]
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  ans=0
  rep=(r-l)//d
  for j in range(rep):
    if T[l+j*d][l+(j+1)*d]!=0:
      ans+=T[l+j*d][l+(j+1)*d]
    else:
      ans+=Dist(l+j*d,l+(j+1)*d)
      T[l+j*d][l+(j+1)*d]=Dist(l+j*d,l+(j+1)*d)
  print(ans)

Submission status: Runtime Error

Solution code:
# ABC089-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
h,w,d=IL()
A=[IL() for i in range(h)]
Al=[0]*(h*w+1)
for i in range(h):
    for j in range(w):
        Al[A[i][j]]=[i,j]

rui={}
for i in range(d):
    T=[0]
    for j in range(1,h*w+1-i-d,d):
        T.append(abs(Al[j+i][0]-Al[j+d+i][0])+abs(Al[j+i][1]-Al[j+d+i][1]))
    for j in range(len(T)-1):
        T[j+1]+=T[j]
    rui[(i+1)%d]=T
q=I()
for w in range(q):
    l,r=IL()
    idx=l%d
    li=l//d
    ri=r//d
    print(rui[idx][ri]-rui[idx][li])

Submission status: Runtime Error

Solution code:
# ABC089-D
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
h,w,d=IL()
A=[IL() for i in range(h)]
Al=[0]*(h*w+1)
for i in range(h):
    for j in range(w):
        Al[A[i][j]]=[i,j]

rui=[]
for i in range(d):
    T=[0]
    for j in range(1,h*w,d):
        T.append(abs(Al[j][0]-Al[j+1][0])+abs(Al[j][1]-Al[j+1][1]))
    for j in range(len(T)-1):
        T[j+1]+=T[j]
    rui.append(T)
q=I()
for w in range(q):
    l,r=IL()
    idx=l%d
    li=l//d
    ri=r//d
    print(rui[idx][ri]-rui[idx][li])

Submission status: Runtime Error

Solution code:
h,w,d=map(int,input().split())
l={}
for i in range(h):
  l1=list(map(int,input().split()))
  for j in l1:
    l[j]=[l1.index(j)+1,i+1]
li=[]
for i in range(1,d+1):
  l11=[]
  c=0
  x=l[i][0]
  y=l[i][1]
  while i<=h*w:
    c+=abs(x-l[i][0])+abs(y-l[i][1])
    l11.append(c)
    x=l[i][0]
    y=l[i][1]
    i+=d
  li.append(l11)
q=int(input())
for i in range(q):
  a,b=map(int,input().split())
  r=a%d
  if r==0:
    print(li[d][b//d-1]-li[d][a//d-1])
  else:
    print(li[r-1][b//d]-li[r-1][a//d])

Submission status: Runtime Error

Solution code:
from math import ceil
H,W,D=map(int,input().split())
A=[[0]*(int(ceil(H*W/D))) for i in range(D)]
for i in range(H):
    Ai=list(map(int,input().split()))
    for j in range(W):

        A[Ai[j]%D][Ai[j]//D]=(i,j)
A[0][0]=(0,0)
B=[[0]*(int(ceil(H*W/D))) for i in range(D)]
for j in range(D):
    for i in range(len(A[0])-1):
        if type(A[j][i+1])!=type((0,0)):
            B[j][i+1]=B[j][i]
            continue
        B[j][i+1]=B[j][i]+abs(A[j][i][0]-A[j][i+1][0])+abs(A[j][i][1]-A[j][i+1][1])
Q=int(input())
for _ in range(Q):
    L,R=map(int,input().split())
    print(B[R%D][R//D]-B[L%D][L//D])

Submission status: Runtime Error

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

        A[Ai[j]%D][Ai[j]//D]=(i,j)
A[0][0]=(0,0)
B=[[0]*(int(ceil(H*W/D))) for i in range(D)]
for j in range(D):
    for i in range(len(A[0])-1):
        if type(A[j][i+1])!=type((0,0)):
            B[j][i+1]=B[j][i]
            continue
        B[j][i+1]=B[j][i]+abs(A[j][i][0]-A[j][i+1][0])+abs(A[j][i][1]-A[j][i+1][1])
Q=int(input())
for _ in range(Q):
    L,R=map(int,input().split())
    print(B[R%D][R//D]-B[L%D][L//D])