Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
Q = int(input())
d = [[0] * (H*W+1) for i in range(H*W+1)]

# 全ての数字に対応する座標を格納
matrix = [[] for i in range(H*W+1)]
for i in range(H):
    for j in range(W):
        matrix[A[i][j]] = (i, j)

#print(matrix)
for i in range(1, H*W+1):
    for j in range(i, H*W+1, D):
        if i == j:
            d[i][j] = 0
        else:
            f = matrix[j-D]
            to = matrix[j]
            d[i][j] = d[i][j-D] + abs(f[0]-to[0]) + abs(f[1]-to[1])
    for j in range(i-D,0,-D):
        f = matrix[j+D]
        to = matrix[j]
        d[i][j] = d[i][j+D] + abs(f[0]-to[0]) + abs(f[1]-to[1])

for i in range(Q):
    l, r = map(int, input().split())
    print(d[l][r])



Fixed submission:
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_list = [[0] * 2 for _ in range(H*W+1)]
for h in range(H):
    for w in range(W):
        number_list[A[h][w]] = [h, w]

d = [0] * (H*W+1)
for idx in range(H*W+1):
    pre_idx = idx - D
    if pre_idx <= 0:
        continue
    diff = abs(number_list[idx][0] - number_list[pre_idx][0])
    diff += abs(number_list[idx][1] - number_list[pre_idx][1])
    d[idx] = d[pre_idx] + diff

for l, r in LR:
    cnt = 0
    print(d[r] - d[l])

Buggy python submission (verdict: Time Limit Exceeded):
H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
Q = int(input())
d = [[0] * (H*W+1) for i in range(H*W+1)]

# 全ての数字に対応する座標を格納
matrix = [[] for i in range(H*W+1)]
for i in range(H):
    for j in range(W):
        matrix[A[i][j]] = (i, j)

#print(matrix)
for i in range(1, H*W+1):
    for j in range(i, H*W+1):
        if (j-i) % D != 0: continue
        if i == j:
            d[i][j] = 0
        else:
            f = matrix[j-D]
            to = matrix[j]
            d[i][j] = d[i][j-D] + abs(f[0]-to[0]) + abs(f[1]-to[1])
    for j in range(i-1,0,-1):
        if (j-i) % D != 0: continue
        f = matrix[j+D]
        to = matrix[j]
        d[i][j] = d[i][j-D] + abs(f[0]-to[0]) + abs(f[1]-to[1])

for i in range(Q):
    l, r = map(int, input().split())
    print(d[l][r])



Fixed submission:
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_list = [[0] * 2 for _ in range(H*W+1)]
for h in range(H):
    for w in range(W):
        number_list[A[h][w]] = [h, w]

d = [0] * (H*W+1)
for idx in range(H*W+1):
    pre_idx = idx - D
    if pre_idx <= 0:
        continue
    diff = abs(number_list[idx][0] - number_list[pre_idx][0])
    diff += abs(number_list[idx][1] - number_list[pre_idx][1])
    d[idx] = d[pre_idx] + diff

for l, r in LR:
    cnt = 0
    print(d[r] - d[l])

Buggy python submission (verdict: Time Limit Exceeded):
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_list = [[] for _ in range(H*W+1)]
for h in range(H):
    for w in range(W):
        number_list[A[h][w]] = [h, w]

for l, r in LR:
    cnt = 0
    while l != r:
        x, y = number_list[l]
        l += D
        nx, ny = number_list[l]
        cnt += (abs(x-nx) + abs(ny - y))
    print(cnt)


Fixed submission:
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_list = [[0] * 2 for _ in range(H*W+1)]
for h in range(H):
    for w in range(W):
        number_list[A[h][w]] = [h, w]

d = [0] * (H*W+1)
for idx in range(H*W+1):
    pre_idx = idx - D
    if pre_idx <= 0:
        continue
    diff = abs(number_list[idx][0] - number_list[pre_idx][0])
    diff += abs(number_list[idx][1] - number_list[pre_idx][1])
    d[idx] = d[pre_idx] + diff

for l, r in LR:
    cnt = 0
    print(d[r] - d[l])