Buggy python submission (verdict: Time Limit Exceeded):
from itertools import chain

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

flat_a = list(chain.from_iterable(A))

S = [0] * (H*W)
for i in reversed(range(H*W-D)):
    tmp1 = flat_a.index(i+1)
    tmp2 = flat_a.index(i+D+1)
    S[i] = abs(tmp1%W - tmp2%W) + abs(tmp1//W - tmp2//W) + S[i + D]

for L, R in exam:
    print(S[L-1] - S[R-1])



Fixed submission:
from itertools import chain

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

x_a = [0] * (H*W)
y_a = [0] * (H*W)

for i, ax in enumerate(A):
    for j, ay in enumerate(ax):
        x_a[ay-1] = i
        y_a[ay-1] = j

S = [0] * (H*W)
for i in reversed(range(H*W-D)):
    S[i] = abs(x_a[i] - x_a[i+D]) + abs(y_a[i] - y_a[i+D]) + S[i + D]

for L, R in exam:
    print(S[L-1] - S[R-1])

Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
exam = [list(map(int, input().split())) for _ in range(Q)]

S = [0] * (H*W)
for i in reversed(range(H*W-D)):
    tmp1 = (0, 0)
    tmp2 = (0, 0)
    for j, Ai in enumerate(A):
        if i+1 in Ai:
            tmp1 = (Ai.index(i+1), j)
        if i+D+1 in Ai:
            tmp2 = (Ai.index(i+D+1), j)
    S[i] = abs(tmp1[0] - tmp2[0]) + abs(tmp1[1] - tmp2[1]) + S[i + D]

for L, R in exam:
    print(S[L-1] - S[R-1])



Fixed submission:
from itertools import chain

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

x_a = [0] * (H*W)
y_a = [0] * (H*W)

for i, ax in enumerate(A):
    for j, ay in enumerate(ax):
        x_a[ay-1] = i
        y_a[ay-1] = j

S = [0] * (H*W)
for i in reversed(range(H*W-D)):
    S[i] = abs(x_a[i] - x_a[i+D]) + abs(y_a[i] - y_a[i+D]) + S[i + D]

for L, R in exam:
    print(S[L-1] - S[R-1])

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import chain

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

Ai = list(chain.from_iterable(A))

def search(x):
    tmp = Ai.index(x)
    return (tmp%W+1,tmp//W+1)

for L, R in exam:
    cost = 0
    nw = L
    nt = L + D
    for _ in range((R-L)//D):
        il, jl = search(nw)
        ir, jr = search(nt)
        nw = nt
        nt = nw + D
        cost += abs(il - ir) + abs(jl - jr)
    print(cost)



Fixed submission:
from itertools import chain

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

x_a = [0] * (H*W)
y_a = [0] * (H*W)

for i, ax in enumerate(A):
    for j, ay in enumerate(ax):
        x_a[ay-1] = i
        y_a[ay-1] = j

S = [0] * (H*W)
for i in reversed(range(H*W-D)):
    S[i] = abs(x_a[i] - x_a[i+D]) + abs(y_a[i] - y_a[i+D]) + S[i + D]

for L, R in exam:
    print(S[L-1] - S[R-1])

Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
exam = [list(map(int, input().split())) for _ in range(Q)]

def search(x):
    j = 0
    for i, Ai in enumerate(A):
        if x in Ai:
            j = Ai.index(x)
            break
    return (i+1,j+1)

for L, R in exam:
    cost = 0
    nw = L
    nt = L + D
    for _ in range((R-L)//D):
        il, jl = search(nw)
        ir, jr = search(nt)
        nw = nt
        nt = nw + D
        cost += abs(il - ir) + abs(jl - jr)
    print(cost)



Fixed submission:
from itertools import chain

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

x_a = [0] * (H*W)
y_a = [0] * (H*W)

for i, ax in enumerate(A):
    for j, ay in enumerate(ax):
        x_a[ay-1] = i
        y_a[ay-1] = j

S = [0] * (H*W)
for i in reversed(range(H*W-D)):
    S[i] = abs(x_a[i] - x_a[i+D]) + abs(y_a[i] - y_a[i+D]) + S[i + D]

for L, R in exam:
    print(S[L-1] - S[R-1])