Buggy python submission (verdict: Time Limit Exceeded):
hwd = list(map(int, input().split()))
a = []
for i in range(hwd[0]):
    a.append(list(map(int, input().split())))
q = int(input())
lr = []
for i in range(q):
    lr.append(list(map(int, input().split())))

xy = [None] * hwd[0] * hwd[1]
for i in range(hwd[0]):
    for j in range(hwd[1]):
        xy[a[i][j] - 1] = [i, j]
for i in range(q):
    power = 0
    pre_number = lr[i][0]
    next_number = lr[i][0] + hwd[2]
    while pre_number != lr[i][1]:
        power = power + abs(xy[pre_number - 1][0] - xy[next_number - 1][0]) + abs(xy[pre_number - 1][1] - xy[next_number - 1][1])
        pre_number = next_number
        next_number = next_number + hwd[2]
    print(power)

Fixed submission:
hwd = list(map(int, input().split()))
a = []
for i in range(hwd[0]):
    a.append(list(map(int, input().split())))
q = int(input())
lr = []
for i in range(q):
    lr.append(list(map(int, input().split())))

xy = [None] * hwd[0] * hwd[1]
for i in range(hwd[0]):
    for j in range(hwd[1]):
        xy[a[i][j] - 1] = [i, j]
        
power_accumulation = []
for i in range(hwd[2]):
    power = [0]
    number = 0
    place = i
    while place < hwd[0] * hwd[1] - hwd[2]:
        power.append(power[number] + abs(xy[place + hwd[2]][0] - xy[place][0]) + abs(xy[place + hwd[2]][1] - xy[place][1]))
        number = number + 1
        place = place + hwd[2]
    power_accumulation.append(power)

for i in range(q):
    test_power = power_accumulation[(lr[i][1] - 1) % hwd[2]][(lr[i][1] - 1) // hwd[2]] - power_accumulation[(lr[i][0]- 1) % hwd[2]][(lr[i][0] - 1) // hwd[2]]
    print(test_power)

Buggy python submission (verdict: Time Limit Exceeded):
hwd = list(map(int, input().split()))
a = []
for i in range(hwd[0]):
    a.append(list(map(int, input().split())))
q = int(input())
lr = []
for i in range(q):
    lr.append(list(map(int, input().split())))

for i in range(q):
    power = 0
    pre_number = lr[i][0]
    next_number = lr[i][0] + hwd[2]
    while pre_number != lr[i][1]:
        for j in range(hwd[0]):
            for k in range(hwd[1]):
                if a[j][k] == pre_number:
                    pre_xy = [j, k]
                if a[j][k] == next_number:
                    next_xy = [j, k]
        power = power + abs(pre_xy[0] - next_xy[0]) + abs(pre_xy[1] - next_xy[1])
        pre_number = next_number
        next_number = next_number + hwd[2]
    print(power)

Fixed submission:
hwd = list(map(int, input().split()))
a = []
for i in range(hwd[0]):
    a.append(list(map(int, input().split())))
q = int(input())
lr = []
for i in range(q):
    lr.append(list(map(int, input().split())))

xy = [None] * hwd[0] * hwd[1]
for i in range(hwd[0]):
    for j in range(hwd[1]):
        xy[a[i][j] - 1] = [i, j]
        
power_accumulation = []
for i in range(hwd[2]):
    power = [0]
    number = 0
    place = i
    while place < hwd[0] * hwd[1] - hwd[2]:
        power.append(power[number] + abs(xy[place + hwd[2]][0] - xy[place][0]) + abs(xy[place + hwd[2]][1] - xy[place][1]))
        number = number + 1
        place = place + hwd[2]
    power_accumulation.append(power)

for i in range(q):
    test_power = power_accumulation[(lr[i][1] - 1) % hwd[2]][(lr[i][1] - 1) // hwd[2]] - power_accumulation[(lr[i][0]- 1) % hwd[2]][(lr[i][0] - 1) // hwd[2]]
    print(test_power)