Buggy python submission (verdict: Time Limit Exceeded):
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)

dp = [[0]*(h*w+1) for x in range(h*w+1)]

def func(a, b):
    if dp[a][b]:
        return dp[a][b]

    for i in range(a, b+1, d):
        if a == b:
            dp[a][b] = 0
            return dp[a][b]
        elif i == a:
            dp[a][i] = 0
        else:
            dp[a][i] = dp[a][i-d] + abs(p[i-d][0]-p[i][0]) + abs(p[i-d][1]-p[i][1])

    for i in range(a, b+1, d):
        for j in range(i, b+1, d):
            dp[i][j] = dp[a][j]-dp[a][i]
    return dp[a][b]

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


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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
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)

dp = [[0]*(h*w+1) for x in range(h*w+1)]

for key in p.keys():
    for i in range(key, h*w+1, d):
        if key == i:
            dp[key][i] = 0
        else:
            dp[key][i] = dp[key][i-d] + abs(p[i-d][0]-p[i][0]) + abs(p[i-d][1]-p[i][1])

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


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

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

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

Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
h, w, d = map(int, input().split())
p = dict()
for i in range(h):
    for j, x in enumerate(map(int, input().split())):
        p[x] = (i, j)

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

def func(a, b):

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


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


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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
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)



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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
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)


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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
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)


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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
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)


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

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

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

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

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


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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
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)


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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
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)


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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
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)


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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
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)


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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
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)


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

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

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

Buggy python submission (verdict: Time Limit Exceeded):
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)


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

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

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