Buggy python submission (verdict: Time Limit Exceeded):
h,w,d = [int (i) for i in input().split()]
index = [[0,0] for i in range(h*w)]
sum = 0
for i in range(h):
    temp = [int(i) for i in input().split()]
    for j in range(w):
        index[temp[j]-1][0] = i
        index[temp[j]-1][1] = j
q = int(input())
empty = []
for i in range(q):
    sum = 0
    a,b = [int (i) for i in input().split()]
    while a != b:
        sum += abs(index[a-1][0] - index[a+d-1][0])+abs(index[a-1][1] - index[a+d-1][1])
        a   += d
    empty.append(sum)

for i in range(q):
    print(empty[i])

Fixed submission:
h,w,d = [int (i) for i in input().split()]
index = [[0,0] for i in range(h*w)]
sum = 0
for i in range(h):
    temp = [int(i) for i in input().split()]
    for j in range(w):
        index[temp[j]-1][0] = i
        index[temp[j]-1][1] = j
q = int(input())
dick = [0 for i in range (h*w)]
for i in range (d,h*w):
    dick[i] = dick[i-d] + abs(index[i][0]-index[i-d][0])+abs(index[i][1]-index[i-d][1])
for i in range(q):
    a,b = [int(i) for i in input().split()]
    print(dick[b-1] - dick[a-1])

Buggy python submission (verdict: Time Limit Exceeded):
h,w,d = [int (i) for i in input().split()]
index = [[0,0] for i in range(h*w)]
sum = 0
for i in range(h):
    temp = [int(i) for i in input().split()]
    for j in range(w):
        index[temp[j]-1][0] = i
        index[temp[j]-1][1] = j
q = int(input())
empty = []
for i in range(q):
    sum = 0
    a,b = [int (i) for i in input().split()]
    c = (b-a)//d
    if c == 0:
        sum = 0
    else:
        for i in range(c):
            sum += abs(index[a-1][0] - index[a+d-1][0])+abs(index[a-1][1] - index[a+d-1][1])
            a   += d
    empty.append(sum)

for i in range(q):
    print(empty[i])

Fixed submission:
h,w,d = [int (i) for i in input().split()]
index = [[0,0] for i in range(h*w)]
sum = 0
for i in range(h):
    temp = [int(i) for i in input().split()]
    for j in range(w):
        index[temp[j]-1][0] = i
        index[temp[j]-1][1] = j
q = int(input())
dick = [0 for i in range (h*w)]
for i in range (d,h*w):
    dick[i] = dick[i-d] + abs(index[i][0]-index[i-d][0])+abs(index[i][1]-index[i-d][1])
for i in range(q):
    a,b = [int(i) for i in input().split()]
    print(dick[b-1] - dick[a-1])

Buggy python submission (verdict: Time Limit Exceeded):
h,w,d = [int (i) for i in input().split()]
index = [[0,0] for i in range(h*w)]
sum = 0
for i in range(h):
    temp = [int(i) for i in input().split()]
    for j in range(w):
        index[temp[j]-1][0] = i
        index[temp[j]-1][1] = j
q = int(input())
for i in range(q):
    sum = 0
    a,b = [int (i) for i in input().split()]
    c = (b-a)//d
    for i in range(c):
        sum += abs(index[a-1][0] - index[a+d-1][0])+abs(index[a-1][1] - index[a+d-1][1])
        a += d
    print(sum)

Fixed submission:
h,w,d = [int (i) for i in input().split()]
index = [[0,0] for i in range(h*w)]
sum = 0
for i in range(h):
    temp = [int(i) for i in input().split()]
    for j in range(w):
        index[temp[j]-1][0] = i
        index[temp[j]-1][1] = j
q = int(input())
dick = [0 for i in range (h*w)]
for i in range (d,h*w):
    dick[i] = dick[i-d] + abs(index[i][0]-index[i-d][0])+abs(index[i][1]-index[i-d][1])
for i in range(q):
    a,b = [int(i) for i in input().split()]
    print(dick[b-1] - dick[a-1])