Buggy python submission (verdict: Time Limit Exceeded):
n,m,d = map(int, input().split())

grid = []

buf = {}

for j in range(n):
    grid.append(list(map(int, input().split())))
    for k in range(len(grid[j])):
        buf[grid[j][k]] = (j,k)
q = int(input())
al = []

for _ in range(q):
    l,r = map(int, input().split())
    al.append([l,r])

for l,r in al:
    s = 0

    for j in range(l,r+1,d):
        if j!=l:
            s+= abs(buf[j][0] - buf[j-d][0]) + abs(buf[j][1] - buf[j-d][1])
    print(s)
            
            

Fixed submission:
n,m,d = map(int, input().split())

grid = []

buf = {}

for j in range(n):
    grid.append(list(map(int, input().split())))
    for k in range(len(grid[j])):
        buf[grid[j][k]] = (j,k)
q = int(input())
al = []

cost = [0] * ((n*m)+1)

for i in range(d+1,n*m+1):
    cost[i] = cost[i-d] + abs(buf[i-d][0] - buf[i][0]) + abs(buf[i-d][1] - buf[i][1])

for _ in range(q):
    l,r = map(int, input().split())
    al.append([l,r])
    

for l,r in al:
    print(cost[r]-cost[l])

Buggy python submission (verdict: Time Limit Exceeded):
n,m,d = map(int, input().split())

grid = []

buf = {}

for j in range(n):
    grid.append(list(map(int, input().split())))
    for k in range(len(grid[j])):
        buf[grid[j][k]] = (j,k)
q = int(input())

for _ in range(q):
    l,r = map(int, input().split())
    s = 0

    for j in range(l,r+1,d):
        if j!=l:
            s+= abs(buf[j][0] - buf[j-d][0]) + abs(buf[j][1] - buf[j-d][1])
    print(s)
            

Fixed submission:
n,m,d = map(int, input().split())

grid = []

buf = {}

for j in range(n):
    grid.append(list(map(int, input().split())))
    for k in range(len(grid[j])):
        buf[grid[j][k]] = (j,k)
q = int(input())
al = []

cost = [0] * ((n*m)+1)

for i in range(d+1,n*m+1):
    cost[i] = cost[i-d] + abs(buf[i-d][0] - buf[i][0]) + abs(buf[i-d][1] - buf[i][1])

for _ in range(q):
    l,r = map(int, input().split())
    al.append([l,r])
    

for l,r in al:
    print(cost[r]-cost[l])

Buggy python submission (verdict: Time Limit Exceeded):
n,m,d = map(int, input().split())

grid = [list(map(int, input().split())) for _ in range(n)]

q = int(input())

buf = {}

for j in range(n):
    for k in range(m):
        buf[grid[j][k]] = (j,k)

for _ in range(q):
    l,r = map(int, input().split())
    prev_x= -1
    prev_y = -1
    s = 0

    for j in range(l,r+1,d):
        if j!=l:
            s+= abs(buf[j][0] - buf[j-d][0]) + abs(buf[j][1] - buf[j-d][1])
    print(s)
            
                


Fixed submission:
n,m,d = map(int, input().split())

grid = []

buf = {}

for j in range(n):
    grid.append(list(map(int, input().split())))
    for k in range(len(grid[j])):
        buf[grid[j][k]] = (j,k)
q = int(input())
al = []

cost = [0] * ((n*m)+1)

for i in range(d+1,n*m+1):
    cost[i] = cost[i-d] + abs(buf[i-d][0] - buf[i][0]) + abs(buf[i-d][1] - buf[i][1])

for _ in range(q):
    l,r = map(int, input().split())
    al.append([l,r])
    

for l,r in al:
    print(cost[r]-cost[l])

Buggy python submission (verdict: Time Limit Exceeded):
n,m,d = map(int, input().split())

grid = [list(map(int, input().split())) for _ in range(n)]

q = int(input())

for _ in range(q):
    l,r = map(int, input().split())
    prev_x= -1
    prev_y = -1
    s = 0

    for j in range(l,r+1,d):
        for k in range(n):
            if j in grid[k]:
                y = (grid[k].index(j))+1
                x = k+1
                break
        if prev_x == -1 and prev_y == -1:
            prev_x = x
            prev_y = y
        else:
            s += abs(prev_x-x) + abs(prev_y-y)
            prev_x = x
            prev_y = y
    print(s)
            
                


Fixed submission:
n,m,d = map(int, input().split())

grid = []

buf = {}

for j in range(n):
    grid.append(list(map(int, input().split())))
    for k in range(len(grid[j])):
        buf[grid[j][k]] = (j,k)
q = int(input())
al = []

cost = [0] * ((n*m)+1)

for i in range(d+1,n*m+1):
    cost[i] = cost[i-d] + abs(buf[i-d][0] - buf[i][0]) + abs(buf[i-d][1] - buf[i][1])

for _ in range(q):
    l,r = map(int, input().split())
    al.append([l,r])
    

for l,r in al:
    print(cost[r]-cost[l])