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: Time Limit Exceeded

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.get(now*H*W+goal,0))

Submission status: Time Limit Exceeded

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]
            print(dic[now*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
    if dic.get(now*H*W+goal,0)==0:
        dic[now*H*W+goal]=ans
        print(ans)

Submission status: Time Limit Exceeded

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]
    if dic.get(now*H*W+goal,0)!=0:
        print(dic[now*H*W+goal])
        continue
    tmp=now
    for j in range((goal-now)//D):
        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+goal]=ans
    print(ans)

Submission status: Time Limit Exceeded

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]
    if dic.get(now*H*W+goal,0)!=0:
        print(ans)
        continue
    for j in range((goal-now)//D):
        now+=D
        x=arr[now][0]
        y=arr[now][1]
        ans+=abs(x-nx)+abs(y-ny)
        nx=x
        ny=y
    dic[now*H*W+goal]=ans
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split())
list1=[]
for i in range(H*W+1):
    list1.append([0,0])

#print(list1)

for j in range(H):
    A=list(map(int,input().split()))
    for k in range(W):
        list1[A[k]][0]=j+1
        list1[A[k]][1]=k+1
#print(list1)

Q=int(input())
for a in range(Q):
    L,R=map(int,input().split())
    cnt=0
    while L<=R:
        if L==R:
            print(cnt)
            break
        else:
            
            cnt+=abs(list1[L+D][0]-list1[L][0])+abs(list1[L+D][1]-list1[L][1])
            L+=D

Submission status: Time Limit Exceeded

Solution code:

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

    #lst = [0 for i in range(n)]
    lst = [[0 for i in range(W)] for j in range(H)]
    for i in range(H):
        lst[i] = list(map(int,input().split()))

    lst = [ y for x in lst for y in x]
    Q = int(input())

    lr=[0 for i in range(Q)]
    for i in range(Q):
        lr[i] = list(map(int,input().split()))


    for i in range(Q):
        start = lr[i][0]
        goal = lr[i][1]
        n = (goal - start)//D
        ans = 0
        for j in range(n):
            h1 = lst.index(start)//W
            w1 = lst.index(start) - (h1*W)
            h2 = lst.index(start+D)//W
            w2 = lst.index(start+D) - (h2*W)
            #print(abs(h2-h1)+abs(w2-w1))
            ans += abs(h2-h1)+abs(w2-w1)
            start = start+D

        print(ans)



if __name__ == "__main__":
        main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
H, W, D = map(int, input().split())
A = [None] * H
B = {}
for i in range(H):
    A[i] = [int(x) for x in input().split()]
    for j, Aij in enumerate(A[i]):
        B[Aij] = (i, j)
costs = defaultdict(list)
for n in range(1, W * H + 1):
    m = n
    costs[n].append(0)
    while m + D < H * W + 1:
        x1, y1 = B[m]
        m += D
        x2, y2 = B[m]
        costs[n].append(abs(x1 - x2) + abs(y1 - y2) + costs[n][-1])

Q = int(input())
for i in range(Q):
    Li, Ri = map(int, input().split())
    n_move = (Ri - Li) // D
    print(costs[Li][n_move])

Submission status: Time Limit Exceeded

Solution code:
H, W, D = (int(i) for i in input().split())

A = [[int(i) for i in input().split()] for i in range(H)]

Q = int(input())

for _ in range(Q):
    L, R = (int(i) for i in input().split())
    ans = 0
    for h in range(H):  # 数字Lを探して初期座標を取得
        if L in A[h]:
            y = A[h].index(L)
            x = h
            break
    a, b = x, y
    for i in range(L+D, R+D, D):
        for h in range(H):  # 数字iを探して座標を取得
            if i in A[h]:
                y = A[h].index(i)
                x = h
                break
        ans += abs(x-a) + abs(y-b)
        a, b = x, y
    print(ans)

Submission status: Time Limit Exceeded

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

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

for _ in range(int(input())):
  a,b=map(int,input().split())
  v=0
  for i in range(a,b,d):
    x1,y1=m[i]
    x2,y2=m[i+d]
    v+=abs(x1-x2)+abs(y1-y2)
  print(v)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W, D = map(int, input().split())
grid = np.array([[0, 0]] * (H * W))
for i in range(H):
    Ai = list(map(int, input().split()))
    for j in range(W):
        grid[Ai[j] - 1] = [i, j]
Q = int(input())
tasks = [list(map(int, input().split())) for _ in range(Q)]

accum = [[]] * D
for i in range(D):
    diff = (abs(np.diff(grid[i::D, 0])) + abs(np.diff(grid[i::D, 1])))
    accum[i] = [0] + list(np.cumsum(diff))

for q in range(Q):
    Li, Ri = tasks[q]
    res = (Li - 1) % D
    x = (Li - 1) // D
    y = (Ri - 1)// D
    print(accum[res][y] - accum[res][x])

Submission status: Time Limit Exceeded

Solution code:
H,W,D = [int(x) for x in input().split()]

d = {}

masu = [[int(x) for x in input().split()] for _ in range(H)]


for y in range(H):
    for x in range(W):
        v=masu[y][x]
        d[v] = (x,y)

Q = int(input())

for _ in range(Q):
    f,t = [int(x) for x in input().split()]
    n = int((t-f)/D)
    mp = 0
    currentV = f
    for _ in range(n):
        prev = d[currentV]
        nxt = d[currentV+D]
        mp += abs(prev[0]-nxt[0])+abs(prev[1]-nxt[1])
        currentV += D
    print(mp)

Submission status: Time Limit Exceeded

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

p = [[] for _ in range(h * w)]

for i in range(h):
    temp = list(map(int, input().split()))
    for j in range(w):
        p[temp[j] - 1] = [i, j]

q = int(input())
a = [[int(x) - 1 for x in input().split()] for _ in range(q)]

for i in range(q):
    temp = 0
    j = a[i][1]
    while j > a[i][0]:
        temp += abs(p[j][0] - p[j - d][0]) + abs(p[j][1] - p[j - d][1])
        j -= d
    print(temp)

Submission status: Time Limit Exceeded

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

p = [[] for _ in range(h * w)]

for i in range(h):
    temp = list(map(int, input().split()))
    for j in range(w):
        p[temp[j] - 1] = [i, j]

q = int(input())
a = [[int(x) - 1 for x in input().split()] for _ in range(q)]

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

for i in range(q):
    temp = 0
    j = a[i][1]
    while j > a[i][0]:
        temp += s[j]
        j -= d
    print(temp)

Submission status: Time Limit Exceeded

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())
for i in range(Q):
    p=0
    L, R=list(map(int, input().split()))
    for j in range((R-L)//D):
        p+=abs(pos[L+D*j][0]-pos[L+D*(j+1)][0])+abs(pos[L+D*j][1]-pos[L+D*(j+1)][1])
    print(p)

Submission status: Time Limit Exceeded

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

for h in range(H):
    L = list(map(int, input().split()))
    for w in range(W):
        position[L[w] - 1] = (h, w)

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    if L == R:
        print(0)
        continue
    
    res = 0
    for i in range(L-1, R - 1, D):
        A = position[i + D]
        B = position[i]
        res += abs(A[0] - B[0]) + abs(A[1] - B[1])
        
    print(res)

Submission status: Time Limit Exceeded

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

    for _ in range(q):
        power = 0
        l, r = map(int, input().split())
        for p in range(l+d, r+1, d):
            power += abs(pre[p][0]-pre[p-d][0])
            power += abs(pre[p][1]-pre[p-d][1])
        print(power)

m()

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split())
hyo=[list(map(int,input().split())) for i in range(H)]
Q=int(input())
def test(L,R):
    ans=0
    root=[[0,0] for i in range((R-L)//D+1)]
    x=[i for i in range(L,R+1,D)]
    for i in range(H):
        for j in range(W):
            for k in range(len(x)):
                if hyo[i][j]==x[k]:
                    root[k]=[i+1,j+1]
    for i in range(len(x)-1):
        ans+=abs(root[i][0]-root[i+1][0])+abs(root[i][1]-root[i+1][1])
    print(ans)
for i in range(Q):
    l,m=map(int,input().split())
    if l==m:
    	print(0)
    else:
    	test(l,m)

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split())
hyo=[list(map(int,input().split())) for i in range(H)]
Q=int(input())
def test(L,R):
    ans=0
    root=[[0,0] for i in range((R-L)//D+1)]
    x=[i for i in range(L,R+1,D)]
    for i in range(H):
        for j in range(W):
            for k in range(len(x)):
                if hyo[i][j]==x[k]:
                    root[k]=[i+1,j+1]
    for i in range(len(x)-1):
        ans+=abs(root[i][0]-root[i+1][0])+abs(root[i][1]-root[i+1][1])
    print(ans)
for i in range(Q):
    l,m=map(int,input().split())
    test(l,m)

Submission status: Time Limit Exceeded

Solution code:
h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
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):
    c = 0
    x = l[i]
    
    
    jkl = 0
    while x != r[i]+d:
        op = 0
        p = 0
        
        while op != 1:
            j = 0
            
            while op != 1 and j != h:
                if x == a[j][p]:
                    jkl +=1
                    
                    if jkl != 1:
                        c = c +  abs(j-ab) + abs(p-bc)
                    ab = j
                    bc = p
                    j = 0
                    p = 0
                    op = 1
                j +=1
            p +=1
        x += d
        
    print(c)

Submission status: Time Limit Exceeded

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)
    
    
    for l, r in LR:
        ans = 0
        while True:
            if l == r:
                break
            i, j = A_[l]
            x, y = A_[l+D]
            l += D
            ans += abs(x-i)
            ans += abs(y-j)
        print(ans)
    



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: Time Limit Exceeded

Solution code:
def main():
  h, w, d = map(int, input().split())
  dic = {}
  for i in range(1, h + 1):
    alst = list(map(int, input().split()))
    for j in range(w):
      dic[alst[j]] = (i, j + 1)
  
  q = int(input())
  for _ in range(q):
    l, r = map(int, input().split())
    ans = 0
    tmpx, tmpy = dic[l]
    while r > l:
      ldx, ldy = dic[l + d]
      ans += abs(tmpx - ldx) + abs(tmpy - ldy)
      l += d
      tmpx, tmpy = ldx, ldy
    print(ans)
  
main()

Submission status: Time Limit Exceeded

Solution code:
h, w, d = map(int, input().split())
xys = [[int(x) for x in input().split()] for _ in range(h)]
q = int(input())
lrs = [tuple(map(int, input().split())) for _ in range(q)]

dict_ = {v:(x, y) for y, row in enumerate(xys) for x, v in enumerate(row)}

def jump_cost(xy, ab):
    x, y = dict_[xy]
    a, b = dict_[ab]
    return abs(x-a) + abs(y-b)

for l, r in lrs:
    print(sum(jump_cost(xy, ab) for xy, ab in zip(range(l, r+1, d), range(l+d, r+1, d))))

Submission status: Time Limit Exceeded

Solution code:
H, W, D=[int(x) for x in str(input()).split()]
A=[[0 for x in range(W+1)]]
for i in range(1,H+1):
  b=[0]
  b+=[int(x) for x in str(input()).split()]
  A.append(b)
Q=int(input())
LR=[[0 for x in range(3)]]
for i in range(1,Q+1):
  b=[0]
  b+=[int(x) for x in str(input()).split()]
  LR.append(b)



B=[0 for x in range(H*W+1)]
for i in range(1,W+1):
  for j in range(1,H+1):
    B[A[j][i]]=[j,i]
ans=[]
for i in range (1,Q+1):
  s=0
  x=LR[i][1]
  while x!=LR[i][2]:
    s+=abs(B[x][0]-B[x+D][0])+abs(B[x][1]-B[x+D][1])
    x+=D
  ans.append(s)
for i in ans:
  print(i)

Submission status: Time Limit Exceeded

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

place = [[0, 0] for _ in range(H * W)]
for h in range(H):
	for w in range(W):
		place[a[h][w] - 1] = [h, w]

cost = [abs(place[i][0] - place[i + d][0]) + abs(place[i][1] - place[i + d][1]) for i in range(H * W - d)]

ans = [[0 for _ in range(H * W)] for _ in range(H * W)]

for i in range(H * W):
	for j in range(i, H * W, d):
		num = 0
		for k in range(i, j, d):
			num += cost[k]
		ans[i][j] = num

Q = int(input())

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

Submission status: Time Limit Exceeded

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

place = [[0, 0] for _ in range(H * W)]
for h in range(H):
	for w in range(W):
		place[a[h][w] - 1] = [h, w]

cost = [abs(place[i][0] - place[i + d][0]) + abs(place[i][1] - place[i + d][1]) for i in range(H * W - d)]

Q = int(input())

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

Submission status: Time Limit Exceeded

Solution code:
x=input().split()
h=int(x[0])
w=int(x[1])
d=int(x[2])
grid=[[]*w for i in range(h)]
for i in range(h):
    y=input().split()
    x=0
    while x<w:
        y[x]=int(y[x])
        x=x+1
    grid[i]=y
coor=[[]*2 for i in range(h*w)]
for i in range(h):
    for j in range(w):
        coor[grid[i][j]-1]=[i,j]
q=int(input())
for ii in range(q):
    x=input().split()
    l=int(x[0])
    r=int(x[1])
    cost=0
    while l!=r:
        cost+=abs(coor[l+d-1][0]-coor[l-1][0])+abs(coor[l+d-1][1]-coor[l-1][1])
        l+=d
    print(cost)

Submission status: Time Limit Exceeded

Solution code:
x=input().split()
h=int(x[0])
w=int(x[1])
d=int(x[2])
grid=[[]*w for i in range(h)]
for i in range(h):
    y=input().split()
    x=0
    while x<w:
        y[x]=int(y[x])
        x=x+1
    grid[i].extend(y)
coor=[[]*2 for i in range(h*w)]
for i in range(h):
    for j in range(w):
        coor[grid[i][j]-1].append(i)
        coor[grid[i][j]-1].append(j)
q=int(input())
for ii in range(q):
    x=input().split()
    l=int(x[0])
    r=int(x[1])
    cost=0
    while l!=r:
        cost+=abs(coor[l+d-1][0]-coor[l-1][0])+abs(coor[l+d-1][1]-coor[l-1][1])
        l+=d
    print(cost)

Submission status: Time Limit Exceeded

Solution code:
h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
q = int(input())
lr = [tuple(map(int,input().split())) for i in range(q)]
idx=[0 for i in range(h*w+1)]
for i in range(h):
    for j in range(w):
        idx[a[i][j]] = (i,j)
def m(x, x_0):
    return abs(x[0]-x_0[0])+ abs(x[1]-x_0[1])
    
for (l, r) in lr:
    ans=0
    while(l != r):
        ans += m(idx[l+d],idx[l])
        l=l+d
    print(ans)

Submission status: Time Limit Exceeded

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

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

for l,r in LR:
    if l == r:
        print(0)
        continue
    if memo[l][r]:
        print(memo[l][r])
        continue
    t = 0
    now = l
    while now != r:
        t += memo[now][now+D]
        now += D
        memo[l][now] = t
    print(t)

Submission status: Time Limit Exceeded

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+1) for _ in range(H*W+1)]
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: Time Limit Exceeded

Solution code:
inf = float('inf')
mod = 10**9+7
from itertools import product, permutations, combinations, combinations_with_replacement
import bisect

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 = {}
for i,i2 in enumerate(A):
    for j,j2 in enumerate(i2):
        d[j2] = (i+1,j+1)

def listsub(t1,t2):
    ret = []
    for n1,n2 in zip(t1,t2):
        ret.append(abs(n1-n2))
    return ret

for L, R in LR:
    result = 0
    for i in range(L, R, D):
        result += sum( listsub(d[i+D],d[i]) )
    print(result)

Submission status: Time Limit Exceeded

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)

for l,r in LR:
    if l == r:
        print(0)
        continue
    print(sum(move[l+D:r+1:D]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W,D = list(map(int, input().split()))
a=[]
for i in range(H):
    a.append(list(map(int, input().split())))

Q=int(input())
lr=[]
for i in range(Q):
    lr.append(list(map(int, input().split())))

for q in range(Q):
    dict={}
    num = lr[q][0]
    magic = []
    magicsum = 0
    for h in range(int((lr[q][1]-lr[q][0])/D) + 1):
        for i in range(H):
            for j in range(W):
                if a[i][j]==num:
                    str = "%d%d" %(i,j)
                    dict[str]=num
                    magic.append([i, j])
                    #print(i,j)
                    if h != 0:
                        magicsum += abs(magic[h][0] - magic[h-1][0] ) + abs(magic[h][1] - magic[h-1][1])
        num += D

    #print(magic)
    print(magicsum)

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split())
A=[]
for i in range(H):
    A.append(list(map(int,input().split())))

Q=int(input())
LR=[]
for i in range(Q):
    LR.append(list(map(int,input().split())))



for j in range(Q):
    Start=LR[j][0]
    gone=[]
    shouhi=0
    while LR[j][1] !=Start:
        for i in range(H):
            for k in range(W):
                if A[i][k]==Start:
                    gone.append((i,k))
                    Start+=D
    for i in range(H):
            for k in range(W):
                if A[i][k]==Start:
                    gone.append((i,k))
    for i in range(len(gone)-1):
        shouhi+=(abs(gone[i][0]-gone[i+1][0])+abs(gone[i][1]-gone[i+1][1]))
    
    print(shouhi)

Submission status: Time Limit Exceeded

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)
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    if L == R:
        print(0)
    else:
        ans = 0
        while L < R:
            ans += abs(d[L+D][0]-d[L][0])+abs(d[L+D][1]-d[L][1])
            L+=D
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
HWD=input()
HWD=HWD.rstrip().split(" ")
H=int(HWD[0])
W=int(HWD[1])
D=int(HWD[2])
 
list1=[[0,0]]*(H*W)
for i in range(H):
    line=input()
    line=line.rstrip().split(" ")
    for j in range(W):
        list1[int(line[j])-1]=[i,j]
#print(list1)
 
 
    
N=int(input())
#print(N)
 
for k in range(N):
    LR=input()
    LR=LR.rstrip().split(" ")
    L=int(LR[0])
    R=int(LR[1])
    
    if L==R:
        print(0)
    else:
        count=0
        for l in range(int((R-L)/D)):
            L1=list1[L-1]
            L2=list1[L+D-1]
            #print(L1)
            #print(L2)
            count=count+abs(list1[L-1][0]-list1[L+D-1][0])+abs(list1[L-1][1]-list1[L+D-1][1])
            L=L+D
        print(int(count))

Submission status: Time Limit Exceeded

Solution code:
HWD=input()
HWD=HWD.rstrip().split(" ")
H=int(HWD[0])
W=int(HWD[1])
D=int(HWD[2])

list1=[[0,0]]*(H*W)
for i in range(H):
    line=input()
    line=line.rstrip().split(" ")
    for j in range(W):
        list1[int(line[j])-1]=[i,j]
#print(list1)


    
N=int(input())
#print(N)

for k in range(N):
    LR=input()
    LR=LR.rstrip().split(" ")
    L=int(LR[0])
    R=int(LR[1])
    
    if L==R:
        print(0)
    else:
        count=0
        for l in range(int((R-L)/D)):
            L1=list1[L-1]
            L2=list1[L+D-1]
            #print(L1)
            #print(L2)
            count=count+((L1[0]-L2[0])**2)**0.5+((L1[1]-L2[1])**2)**0.5
            L=L+D
        print(int(count))

Submission status: Time Limit Exceeded

Solution code:
HWD=input()
HWD=HWD.rstrip().split(" ")
H=int(HWD[0])
W=int(HWD[1])
D=int(HWD[2])

list1=[]
for i in range(H):
    list2=[]
    line=input()
    line=line.rstrip().split(" ")
    for j in range(W):
        
        list2.append(int(line[j]))
    list1.append(list2)
#print(list1)


    
N=int(input())
#print(N)

for k in range(N):
    LR=input()
    LR=LR.rstrip().split(" ")
    L=int(LR[0])
    R=int(LR[1])
    if L==R:
        print(0)
    else:
        count=0
        for l in range(int((R-L)/D)):
            
            a=0
            for a in range(H):
                if L in list1[a]:
                    L1=[a+1,list1[a].index(L)+1]
            b=0    
            for b in range(H):
                if L+D in list1[b]:
                    L2=[b+1,list1[b].index(L+D)+1]
            
            count=count+((L1[0]-L2[0])**2)**0.5+((L1[1]-L2[1])**2)**0.5
            L=L+D
        print(int(count))

Submission status: Time Limit Exceeded

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


for i in range(Q):
    power = 0
    for j in range(int((R[i] - L[i]) / D)):
        power += consumption(A[L[i] + j * D - 1], A[L[i] + (j + 1) * D - 1])
        #print("{}->{}".format(A[L[i] + j * D - 1], A[L[i] + (j + 1) * D - 1]))
    print(power)

Submission status: Time Limit Exceeded

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 = []
for i in range(Q):
  syo = b[i,0]
  go = b[i,1]
  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)
for i in range(Q):
  print(ans[i])

Submission status: Time Limit Exceeded

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

q = int(input())
for _ in range(q):
    ans = 0
    l, r = map(int, input().split())

    m = list(range(l, r + 1, d))
    for i in range(len(m) - 1):
        x1, y1 = xy[m[i]]
        x2, y2 = xy[m[i + 1]]
        ans += abs(x1 - x2) + abs(y1 - y2)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = [int(x) for x in input().split()]

def calc_costs(points, d):
    costs = [0] * len(points)
    for i in range(d, len(points)):
        curr = points[i]
        prev = points[i - d]
        costs[i] = abs(curr[0] - prev[0]) + abs(curr[1] - prev[1])
    return costs

def main():
    size = H * W
    points = [None] * size
    for j in range(H):
        for i, x in enumerate(input().split()):
            points[int(x) - 1] = (i, j)

    costs = calc_costs(points, D)

    q = int(input())
    cached = []
    for _ in range(q):
        l, r = map(lambda x: int(x) - 1, input().split())
        ans = 0
        if l == r:
            print(ans)
            continue
        while l < r:
            cache = [l]
            l += D
            cache.append(l)
            if l > size:
                break
            ans += costs[l]
            cache.append(ans)
            cached.append(cache)
        print(ans)

    # print(cached)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W, D = [int(x) for x in input().split()]

def calc_costs(points, d):
    costs = [0] * len(points)
    for i in range(d, len(points)):
        curr = points[i]
        prev = points[i - d]
        costs[i] = abs(curr[0] - prev[0]) + abs(curr[1] - prev[1])
    return costs

def main():
    size = H * W
    points = [None] * size
    for j in range(H):
        for i, x in enumerate(input().split()):
            points[int(x) - 1] = (i, j)

    costs = calc_costs(points, D)

    q = int(input())
    answers = []
    for _ in range(q):
        l, r = map(lambda x: int(x) - 1, input().split())
        ans = 0
        while l < r:
            l += D
            if l > size:
                break
            ans += costs[l]
        answers.append(str(ans))
    print('\n'.join(answers))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

tate = d
yoko = h * w // d + 1

a_h = [[0] * yoko for i in range(tate)]
a_w = [[0] * yoko for i in range(tate)]

for i in range(h):
    a_list = list(map(int, input().split()))
#     print(a_list)
    for j,a in enumerate(a_list):
        syou = a // d
        amari = a % d
#         print(syou,amari)
        a_h[amari][syou] = i
#         print("a_h",a_h)
        a_w[amari][syou] = j
#         print("a_w",a_w)

a_h_a = np.array(a_h)
a_w_a = np.array(a_w)

def diffarray(a):
    return np.abs(a[:,1:] - a[:,:-1])

def amarisyou(num):
    amari = num % d
    syou  = num // d
    return amari, syou

diffh = diffarray(a_h_a)
diffw = diffarray(a_w_a)

q = int(input())

for i in range(q):
    l, r = map(int,input().split())
    
    start_amari, start_syou = amarisyou(l)
    end_amari,   end_syou = amarisyou(r)
    
#     diffh[start_amari, start_syou:end_syou]
#     diffw[start_amari, start_syou:end_syou]
    
    cost = np.sum(diffh[start_amari, start_syou:end_syou]) + np.sum(diffw[start_amari, start_syou:end_syou])
    print(cost)