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

q = int(input())
for i in range(q):
    a, b = map(int, input().split())
    ans = 0
    s, t = p[a]
    while a <= b:
        i, j = p[a]
        ans += abs(s-i)+abs(t-j)
        s, t = i, j
        a += d
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
input=sys.stdin.readline
from copy import deepcopy
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)
        D[x%d].append(p[x])

for key in D.keys():
    D[key].sort()

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

Submission status: Time Limit Exceeded

Solution code:
import heapq
import sys
input=sys.stdin.readline
from copy import deepcopy
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 = deepcopy(D[a%d])
    ans = 0
    while v:
        x, i, j = heapq.heappop(v)
        if x == a:
            s, t = i, j
        if a <= x <= b:
            ans += abs(s-i)+abs(t-j)
            s, t = i, j
            if x == b:
                break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
import bisect
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)
        D[x%d].append((x, i, j))

for key in D.keys():
    D[key].sort()

q = int(input())
for i in range(q):
    a, b = map(int, input().split())
    v = D[a%d]
    l = v.index(p[a])
    r = l + (b-a)//d
    tmp = v[l:r+1]
    _, s, t = tmp[0]
    ans = 0
    for _, u, v in tmp[1:]:
        ans += abs(u-s)+abs(v-t)
        s, t = u, v
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
import bisect
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)
        idx = bisect.bisect_left(D[x%d], (x, i, j))
        D[x%d].insert(idx, (x, i, j))
q = int(input())

for i in range(q):
    a, b = map(int, input().split())
    v = D[a%d]
    l = v.index(p[a])
    r = l + (b-a)//d
    tmp = v[l:r+1]
    _, s, t = tmp[0]
    ans = 0
    for _, u, v in tmp[1:]:
        ans += abs(u-s)+abs(v-t)
        s, t = u, v
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
from collections import defaultdict
h, w, d = map(int, input().split())

I = defaultdict(list)
D = defaultdict(list)
for i in range(h):
    for j, x in enumerate(map(int, input().split())):
        I[x%d].append(x)
        D[x%d].append((x, i, j))
q = int(input())

for key in D.keys():
    I[key].sort()
    D[key].sort()

for i in range(q):
    a, b = map(int, input().split())
    u = I[a%d]
    v = D[a%d]
    l = u.index(a)
    r = u.index(b)
    tmp = v[l:r+1]
    _, s, t = tmp[0]
    ans = 0
    for _,  u, v in tmp[1:]:
        ans += abs(u-s)+abs(v-t)
        s, t = u, v
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
h, w, d = map(int, input().split())

I = defaultdict(list)
D = defaultdict(list)
for i in range(h):
    for j, x in enumerate(map(int, input().split())):
        I[x%d].append(x)
        D[x%d].append((x, i, j))
q = int(input())

for key in D.keys():
    I[key].sort()
    D[key].sort()

for i in range(q):
    a, b = map(int, input().split())
    u = I[a%d]
    v = D[a%d]
    l = u.index(a)
    r = u.index(b)
    tmp = v[l:r+1]
    _, s, t = tmp[0]
    ans = 0
    for _,  u, v in tmp[1:]:
        ans += abs(u-s)+abs(v-t)
        s, t = u, v
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
h, w, d = map(int, input().split())
D = defaultdict(list)
for i in range(h):
    for j, x in enumerate(map(int, input().split())):
        D[x%d].append((x, i, j))
q = int(input())
for i in range(q):
    a, b = map(int, input().split())
    tmp = sorted([x for x in D[a%d] if b>= x[0] >= a])
    _, s, t = tmp[0]
    ans = 0
    for _,  u, v in tmp[1:]:
        ans += abs(u-s)+abs(v-t)
        s, t = u, v
    print(ans)

Submission status: Time Limit Exceeded

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

q = int(input())
for _ in range(q):
  ans = 0
  ansd = {}
  l, r = map(int, input().split())
  if (l, r) in ansd:
    print(ansd[(l, r)])
  else:
    prevx, prevy = amd[l]
    for x in range(l+d, r+1, d):
      _x, _y = amd[x]
      ans += abs(_x - prevx) + abs(_y - prevy)
      prevx, prevy = _x, _y
    print(ans)
    ansd[(l, r)] = ans

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    input = sys.stdin.readline
    H, W, D = map(int, input().split())
    d = {}

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

    A = [[0 for _ in range(H*W+1)] for _ in range(H*W+1)]
    for r in range(H * W, 0, -1):
        for l in range(r - D, 0, -D):
            a = d[l]
            b = d[l+D]
            A[l][r] = A[l+D][r] + abs(a[0] - b[0]) + abs(a[1] - b[1])

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    input = sys.stdin.readline
    H, W, D = map(int, input().split())
    d = {}

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

    A = [[0 for _ in range(H*W)] for _ in range(H*W)]
    for i in range(H * W):
        for j in range(i + D, H * W):
            ans = 0
            L, R = i + 1, j + 1
            if (R - L) % D != 0:
                continue
            while L != R:
                a = d[L]
                b = d[L+D]
                ans += abs(a[0] - b[0]) + abs(a[1] - b[1])
                L += D
            A[i][j] = ans

    Q = int(input())
    for _ in range(Q):
        L, R = map(int, input().split())
        print(A[L-1][R-1])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
    input = sys.stdin.readline
    H, W, D = map(int, input().split())
    d = {}

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

    Q = int(input())
    for _ in range(Q):
        ans = 0
        L, R = map(int, input().split())
        while L != R:
            a = d[L]
            b = d[L+D]
            ans += abs(a[0] - b[0]) + abs(a[1] - b[1])
            L += D
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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)]
for l, r in LR:
    n = 0
    for i in range(l, r, D):
        n += abs(A[i][0] - A[i + D][0]) + abs(A[i][1] - A[i + D][1])
    print(n)

Submission status: Time Limit Exceeded

Solution code:
# D
h, w, d = map(int, input().split())
points = [[0]*2 for i in range(h*w + 1)]
for h_i in range(h):
    a_row = [int(i) for i in input().split()]
    for r_i, a in enumerate(a_row):
        points[a][0] = h_i
        points[a][1] = r_i

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    ans = 0
    while l != r:
        next_l = l + d
        ans += abs(points[l][0] - points[next_l][0]) + abs(points[l][1] - points[next_l][1])
        l = next_l
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w, d = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
quest = [tuple(map(int, input().split())) for _ in range(q)]
enumboard = []
for i in range(h):
    for j in range(w):
        enumboard.append((board[i][j], i, j))
enumboard.sort(key = lambda x: x[0])
for l, r in quest:
    ret = 0
    for x in range(l, r, d):
        ret += abs(enumboard[x+d-1][1] - enumboard[x-1][1]) + abs(enumboard[x+d-1][2] - enumboard[x-1][2])
    print(ret)

Submission status: Time Limit Exceeded

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

note = [0]*(H*W+1)
for i in range(H):
    for j in range(W):
        A = grid[i][j]
        note[A] = (i,j)

def cal(n):
    s = info[n][0]; e = info[n][1]
    cost = 0
    for A in range(s,e-D+1,D):
        i,j = note[A]; ni,nj = note[A+D]
        cost += abs(ni-i) + abs(nj-j)
    return cost

for i in range(Q):
    print(cal(i))

Submission status: Time Limit Exceeded

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

List = [[0, 0] for i in range(H * W)]
for i in range(H):
  for j in range(W):
    List[A[i][j] - 1] = [i, j]
    
Data = [0 for i in range(H * W)]
for i in range(D):
  for j in range(i, H * W - D, D):
    a = List[j]
    b = List[j + D]
    Data[j] = abs(a[0] - b[0]) + abs(a[1] - b[1])
    
Ans = [[0 for i in range(H * W)] for j in range(H * W)]
for i in range(H * W - D):
  t = Data[i]
  for j in range(i + D, H * W, D):
    Ans[i][j] = t
    t += Data[j]
    
for i in range(Q):
  print(Ans[LR[i][0] - 1][LR[i][1] - 1])

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
H,W,D = map(int, input().split())
m = [ list(map(int, input().split())) for _ in range(H)]
Q = int(input())
pos = {}

for h in range(H):
    for w in range(W):
        pos[m[h][w]] = (h,w)
        



d = {}


for i in range(1, 1+D):
    bhop = i
    hop = i + D
    while hop <= H*W:
        d[hop] = abs( pos[hop][0] - pos[bhop][0]) + abs( pos[hop][1] - pos[bhop][1]) 
        bhop = hop
        hop  = hop+D


for i in range(Q):
    L,R = map(int, input().split())
    ans = 0
    hop = L+D
    bhop = L
    while hop <= R:
        ans += d[hop]
        bhop = hop
        hop  = hop+D

    print(ans)

Submission status: Time Limit Exceeded

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(H*W-D):
    dist[i] = 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
    while a+D <= b:
        ans += dist[a]
        a += D
    ans_list[i] = ans

for ans in ans_list:
    print(ans)

Submission status: Time Limit Exceeded

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(H*W):
    if i+D < H*W:
        dist[i] = 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
    while a+D <= b:
        ans += dist[a]
        a += D
    ans_list[i] = ans

for ans in ans_list:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def cul_dis(start,goal):
    return abs(start[0]-goal[0])+abs(start[1]-goal[1])

H,W,d = map(int,input().split())
number_pos = {}

for h in range(H) :
    state = list(map(int,input().split()))
    for i,number in enumerate(state):
        number_pos[number] = [h,i]

Q = int(input())

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

for [L,R] in exams:
    mp = 0
    now_number = L
    while(now_number!=R):
        next_number = now_number+d
        mp += cul_dis(number_pos[now_number],number_pos[next_number])
        now_number = next_number
    print(mp)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys

sys.setrecursionlimit(10 ** 7)

h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
l, r = [], []
for _ in range(q):
    x, y = map(int, input().split())
    l.append(x)
    r.append(y)


coordinates = {a[x][y] : (x, y) for x, y in itertools.product(range(h), range(w))}
cache = {}
def f(x, y):
    if x == y:
        return 0

    key = (x, y)
    if not key in cache:
        i1, j1 = coordinates[x]
        i2, j2 = coordinates[x + d]
        cache[key] = abs(i1 - i2) + abs(j1 - j2) + f(x + d, y)

    return cache[key]


for i in range(q):
    print(f(l[i], r[i]))

Submission status: Time Limit Exceeded

Solution code:
import itertools

h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
l, r = [], []
for _ in range(q):
    x, y = map(int, input().split())
    l.append(x)
    r.append(y)

coordinates = {a[x][y] : (x, y) for x, y in itertools.product(range(h), range(w))}
for i in range(q):
    score = 0
    while l[i] != r[i]:
        x1, y1 = coordinates[l[i]]
        x2, y2 = coordinates[l[i] + d]
        score += abs(x1 - x2) + abs(y1 - y2)
        l[i] = l[i] + d
    print(score)

Submission status: Time Limit Exceeded

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

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

q = int(input())
for i in range(q):
    L,R = map(int,input().split())
    a = list(range(L,R+1,d))
    
    total = 0
    for j in range(len(a)-1):
        total += abs(hw[a[j+1]-1][0] - hw[a[j]-1][0]) + abs(hw[a[j+1]-1][1] - hw[a[j]-1][1])        
        
    print(total)

Submission status: Time Limit Exceeded

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

q = int(input())
a = []
c = []
for i in range(q):
    L,R = map(int,input().split())
    b = list(range(L,R+1,d))
    
    x = 0
    for hw in HW:
        y = 0
        for num in hw:
            if num in b:
                c.append([num,[x+1,y+1]])
            y += 1
        x += 1
    c.sort()
    
    total = 0
    for j in range(len(b)-1):
        total += abs(c[j+1][1][0] - c[j][1][0]) + abs(c[j+1][1][1] - c[j][1][1])        
        
    print(total)

Submission status: Time Limit Exceeded

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

Q=int(input())

for _ in range(Q):
    ans=0
    L,R=map(int,input().split())
    i,j=dic[L]
    for k in range((R-L)//D):
        x,y=dic[L+D*(k+1)]
        ans+=abs(x-i)+abs(y-j)
        i,j=(x,y)
    print(ans)

Submission status: Time Limit Exceeded

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

dic=dict()
from itertools import product
for i,j in product(range(H),range(W)):
    dic[A[i][j]]=(i,j)

for _ in range(Q):
    ans=0
    L,R=map(int,input().split())
    i,j=dic[L]
    for k in range((R-L)//D):
        x,y=dic[L+D*(k+1)]
        ans+=abs(x-i)+abs(y-j)
        i,j=(x,y)
    print(ans)

Submission status: Time Limit Exceeded

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[i], R[i]))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Solution code:
ANS = dict()


def f(l, r):
    if (l, r) in ANS:
        return ANS[l, r]
    n = l
    ans = 0
    while (n != r):
        ans += (abs(P[n][0] - P[n + D][0]) + abs(P[n][1] - P[n + D][1]))
        n += D
    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())

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

Submission status: Time Limit Exceeded

Solution code:
def f(l, r):
    n = l
    ans = 0
    while (n != r):
        ans += (abs(P[n][0] - P[n + D][0]) + abs(P[n][1] - P[n + D][1]))
        n += D
    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())

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

G = [[0, 0]] * (H * W + 1)

for i, j in itertools.product(range(H), range(W)):
    G[A[i][j]] = [i, j]

for l, r in LR:
    ans = 0
    x1, y1 = G[l]
    for i in range(l, r, D):
        x0, y0 = G[i]
        x1, y1 = G[i + D]
        ans += abs(x1 - x0) + abs(y1 - y0)
    print(ans)

Submission status: Time Limit Exceeded

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

Q=int(input())
for x in range(Q):
    L,R=map(int,input().split())
    P=A[L]
    if L==R:
        print(0)
    else:
        ans=0
        for y in range(H*W):
            if L+(y+1)*D==R:
                ans+=(abs(A[L+y*D][0]-A[L+(y+1)*D][0])+abs(A[L+y*D][1]-A[L+(y+1)*D][1]))
                print(ans)
                break
            else:
                ans+=(abs(A[L+y*D][0]-A[L+(y+1)*D][0])+abs(A[L+y*D][1]-A[L+(y+1)*D][1]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
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)]

xy = {}
for h in range(H):
    for w in range(W):
        xy[A[h][w]] = (h,w)

for l,r in LR:
    if l == r:
        print(0)
        continue

    start = l
    cost = 0
    while start != r:
        x,y = xy[start]
        i,j = xy[start+D]
        cost += abs(x-i) + abs(y-j)
        start += D

    print(cost)

Submission status: Time Limit Exceeded

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)

for qq in range(int(input())):
  l, r = map(int, input().split())
  cost = 0
  cur = vals[l]
  while l != r:
    l += d
    nxt = vals[l]
    cost += abs(nxt[0]-cur[0]) + abs(nxt[1]-cur[1])
    cur = nxt
  print(cost)

Submission status: Time Limit Exceeded

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

for i in range(1,H+1):
    s=list(map(int,input().split()))
    for j in range(1,W+1):
        Li.append([s[j-1],i,j])
Li.sort()
#print(Li)
Q=int(input())
for x in range(Q):
     L,R=map(int,input().split())
     sum=0
     for y in range(1000000):
         if L==R:
             print(sum)
             break
         else:
             sum+=abs(Li[L-1][1]-Li[L-1+D][1])+abs(Li[L-1][2]-Li[L-1+D][2])
             L+=D

Submission status: Time Limit Exceeded

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())
ans=0
for q in range(Q):
  l,r=map(int,input().split())
  for k in range((r-l)//D):
    x1=A[l+D*k-1][0]
    x2=A[l+D*(k+1)-1][0]
    y1=A[l+D*k-1][1]
    y2=A[l+D*(k+1)-1][1]
    ans+=abs(x1-x2)
    ans+=abs(y1-y2)
  print(ans)
  ans=0

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
C = {}
for i in range(H):
    A = [int(i) for i in input().split()]
    for j in range(W):
        C[A[j]] = (i, j)

memo = {}
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    if (l, r) in memo:
        print(memo[(l, r)])
    else:
        MP, now = 0, l
        while now < r:
            nowx, nowy = C[now]
            nextx, nexty = C[now + D]
            MP += abs(nowx-nextx) + abs(nowy-nexty)
            now += D
        print(MP)
        memo[(l, r)] = MP

Submission status: Time Limit Exceeded

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

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[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(0,h*w,d):
            if w*i+j + d + k < h*w:
                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)
            else:
                break

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

Submission status: Time Limit Exceeded

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

nc = dict()
for row in range(h):
    for col in range(w):
        v = A[row][col]
        nc[v] = (row, col)

q = int(input())
lrs = [list(map(int, input().split())) for _ in range(q)]

for lr in lrs:
    l, r = lr
    ans = 0
    while l != r:
        i, j = nc[l]
        x, y = nc[l + d]
        ans += abs(x - i) + abs(y - j)
        l += d
    print(ans)

Submission status: Time Limit Exceeded

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

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)]
num_pos = {}

for y, line in enumerate(A):
    for x, num in enumerate(line):
        num_pos[num] = (x, y)

cost_table = {i: {} for i in num_pos.keys()}
for num1 in range(1, H*W+1):
    for num2 in range(num1, H*W+1, D):
        if num1 == num2:
            cost_table[num1][num2] = 0
        else:
            i, j = num_pos[num2-D]
            x, y = num_pos[num2]
            cost_table[num1][num2] = abs(i - x) + abs(j - y) + cost_table[num1][num2-D]

for l, r in LR:
    print(cost_table[l][r])

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)]
num_pos = {}

for y, line in enumerate(A):
    for x, num in enumerate(line):
        num_pos[num] = (x, y)

cost_table = {i: {} for i in num_pos.keys()}
for num1 in sorted(num_pos.keys()):
    for num2 in range(num1, H*W+1, D):
        if num1 == num2:
            cost_table[num1][num2] = 0
        else:
            i, j = num_pos[num2-D]
            x, y = num_pos[num2]
            cost_table[num1][num2] = abs(i - x) + abs(j - y) + cost_table[num1][num2-D]

for l, r in LR:
    print(cost_table[l][r])

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)]
num_pos = {}

for y, line in enumerate(A):
    for x, num in enumerate(line):
        num_pos[num] = (x, y)

for l, r in LR:
    cost = 0
    for d in range(0, r-l, D):
        cost += abs(num_pos[l+d][0] - num_pos[l+d+D][0]) + abs(num_pos[l+d][1] - num_pos[l+d+D][1])
    print(cost)

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 = []
memo = [0] * (H*W+1)
for i in range(D):
  while i < H*W:
    c = np.where(a == i+1)
    i += D
    if i >= H*W:
      break
    d = np.where(a == i+1)
    memo[i] = memo[i-D]  + abs(c[0][0] - d[0][0]) + abs(c[1][0] - d[1][0])
for i in range(Q):
  syo = b[i,0]
  go = b[i,1]
  print(memo[go-1] - memo[syo-1])

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 = []
memo = {}
for i in range(Q):
  syo = b[i,0]
  go = b[i,1]
  if (str(syo)+ " " + str(go)) in memo:
    ans.append(memo[str(syo)+ " " + str(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[str(syo)+ " " + str(go)] = syouhi
for i in range(Q):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
h, w, d = list(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)]

a_and_pos = {}
for i in range(h):
    for j in range(w):
        a_and_pos[a[i][j]] = (i, j)

for l, r in lr:
    ans = 0
    x = l
    i, j = a_and_pos[l]
    while x != r:
        i_next, j_next = a_and_pos[x+d]
        ans = ans +  abs(i_next-i) + abs(j_next-j)
        i, j = i_next, j_next
        x += d
    print(ans)