Buggy python submission (verdict: Time Limit Exceeded):
h,w,d = map(int,input().split())
arr = []
for i in range(h):
    tmp_list = list(map(int,input().split()))
    arr.append(tmp_list)
q = int(input())
querry = []
for i in range(q):
    querry.append(list(map(int,input().split())))
num_list = [[0]*2 for i in range(h*w + 1)]
for i in range(h):
    for j in range(w):
        num_list[arr[i][j]] = [i,j]
cost_list = [0]*(h*w + 1)
for i in range(1,h*w):
    while i <= h*w - d:
        if cost_list[i + d] == 0:
            x0 = num_list[i][0]
            x1 = num_list[i + d][0]
            y0 = num_list[i][1]
            y1 = num_list[i + d][1]
            cost_list[i + d] += cost_list[i] + abs(x0-x1) +  abs(y0-y1)
        i += d
for l,r in querry:
    print(cost_list[r] - cost_list[l])

Fixed submission:
h,w,d = map(int,input().split())
arr = []
for i in range(h):
    tmp_list = list(map(int,input().split()))
    arr.append(tmp_list)
q = int(input())
querry = []
for i in range(q):
    querry.append(list(map(int,input().split())))
num_list = [[0]*2 for i in range(h*w + 1)]
for i in range(h):
    for j in range(w):
        num_list[arr[i][j]] = [i,j]
cost_list = [0]*(h*w + 1)
for i in range(1,h*w):
    for r in range(h*w):
        if i > h*w - d:
            break
        if cost_list[i + d] == 0:
            x0 = num_list[i][0]
            x1 = num_list[i + d][0]
            y0 = num_list[i][1]
            y1 = num_list[i + d][1]
            cost_list[i + d] += cost_list[i] + abs(x0-x1) +  abs(y0-y1)
        else:
            break
        i += d
for l,r in querry:
    print(cost_list[r] - cost_list[l])

Buggy python submission (verdict: Time Limit Exceeded):
h,w,d = map(int,input().split())
arr = []
for i in range(h):
    tmp_list = list(map(int,input().split()))
    arr.append(tmp_list)
q = int(input())
querry = []
for i in range(q):
    querry.append(list(map(int,input().split())))
num_list = [[0]*2 for i in range(h*w + 1)]
for i in range(h):
    for j in range(w):
        num_list[arr[i][j]] = [i,j]
cost_list = [0]*(h*w + 1)
for i in range(1,h*w):
    while i <= h*w - d:
        if cost_list[i + d] == 0:
            x0 = num_list[i][0]
            x1 = num_list[i + d][0]
            y0 = num_list[i][1]
            y1 = num_list[i + d][1]
            cost_list[i + d] += cost_list[i] + abs(x0-x1) +  abs(y0-y1)
        i += d
for l,r in querry:
    print(cost_list[r] - cost_list[l])

Fixed submission:
h,w,d = map(int,input().split())
arr = []
for i in range(h):
    tmp_list = list(map(int,input().split()))
    arr.append(tmp_list)
q = int(input())
querry = []
for i in range(q):
    querry.append(list(map(int,input().split())))
num_list = [[0]*2 for i in range(h*w + 1)]
for i in range(h):
    for j in range(w):
        num_list[arr[i][j]] = [i,j]
cost_list = [0]*(h*w + 1)
for i in range(1,h*w):
    for r in range(h*w):
        if i > h*w - d:
            break
        if cost_list[i + d] == 0:
            x0 = num_list[i][0]
            x1 = num_list[i + d][0]
            y0 = num_list[i][1]
            y1 = num_list[i + d][1]
            cost_list[i + d] += cost_list[i] + abs(x0-x1) +  abs(y0-y1)
        else:
            break
        i += d
for l,r in querry:
    print(cost_list[r] - cost_list[l])