Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
INF = 10 ** 9
MOD = 10 ** 9 + 7

def main(): 
    h,w,d = map(int,input().split())
    n = h * w

    idx = [0]*(1+n)
    for i in range(h):
        a = tuple(map(int,input().split()))
        for j in range(w):
            idx[a[j]] = (i + 1 , j + 1)
    idx[0] = idx[d]

    D = [[0]*(n+1) for _ in range(n+1)]
    
    def dist(i,j):
        return abs(idx[i][0] - idx[j][0]) + abs(idx[i][1] - idx[j][1])
        
    for i in range(d):
        for j in range(i,n - d + 1,d):
            D[j + d][i] = D[j][i] + dist(j,j + d)
    
    q = int(input())
    for _ in range(q):
        l,r = map(int,input().split())
        modd = l%d
        print(D[r][modd] - D[l][modd])        

if __name__=='__main__':
    main()

Fixed submission:
import sys
input = sys.stdin.readline
INF = 10 ** 9
MOD = 10 ** 9 + 7

def main(): 
    h,w,d = map(int,input().split())
    n = h * w

    idx = [0]*(1+n)
    for i in range(h):
        a = tuple(map(int,input().split()))
        for j in range(w):
            idx[a[j]] = (i + 1 , j + 1)
    idx[0] = idx[d]

    D = [0] * (n + 1)
    
    def dist(i,j):
        return abs(idx[i][0] - idx[j][0]) + abs(idx[i][1] - idx[j][1])
        
    for i in range(d):
        for j in range(i,n - d + 1,d):
            D[j + d] = D[j] + dist(j,j + d)
    
    q = int(input())
    for _ in range(q):
        l,r = map(int,input().split())
        print(D[r] - D[l])        

if __name__=='__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
INF = 10 ** 9
MOD = 10 ** 9 + 7

def main(): 
    h,w,d = map(int,input().split())
    n = h * w

    idx = [0]*(1+n)
    for i in range(1,h+1):
        a = tuple(map(int,input().split()))
        for j in range(w):
            idx[a[j]] = (i,j+1)
    idx[0] = idx[d]

    D = [[0]*(n+1) for _ in range(n+1)]
    
    def dist(i,j):
        return abs(idx[i][0] - idx[j][0]) + abs(idx[i][1] - idx[j][1])
        
    for i in range(d):
        num = i
        while num <= n - d:
            D[num + d][i] = D[num][i] + dist(num,num + d)
            num += d
    
    q = int(input())
    for _ in range(q):
        l,r = map(int,input().split())
        modd = l%d
        print(D[r][modd] - D[l][modd])        

if __name__=='__main__':
    main()

Fixed submission:
import sys
input = sys.stdin.readline
INF = 10 ** 9
MOD = 10 ** 9 + 7

def main(): 
    h,w,d = map(int,input().split())
    n = h * w

    idx = [0]*(1+n)
    for i in range(h):
        a = tuple(map(int,input().split()))
        for j in range(w):
            idx[a[j]] = (i + 1 , j + 1)
    idx[0] = idx[d]

    D = [0] * (n + 1)
    
    def dist(i,j):
        return abs(idx[i][0] - idx[j][0]) + abs(idx[i][1] - idx[j][1])
        
    for i in range(d):
        for j in range(i,n - d + 1,d):
            D[j + d] = D[j] + dist(j,j + d)
    
    q = int(input())
    for _ in range(q):
        l,r = map(int,input().split())
        print(D[r] - D[l])        

if __name__=='__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
INF = 10 ** 9
MOD = 10 ** 9 + 7

def main(): 
    h,w,d = map(int,input().split())
    n = h * w

    idx = [0]*(1+n)
    for i in range(1,h+1):
        a = tuple(map(int,input().split()))
        for j in range(w):
            idx[a[j]] = (i,j+1)
    idx[0] = idx[d]

    D = [[0]*(n+1) for _ in range(n+1)]
    
    def dist(i,j):
        return abs(idx[i][0] - idx[j][0]) + abs(idx[i][1] - idx[j][1])
        
    for i in range(d):
        num = i
        while num <= n - d:
            D[num + d][i] = D[num][i] + dist(num,num + d)
            num += d
    
    q = int(input())
    for _ in range(q):
        l,r = map(int,input().split())
        modd = l%d
        print(D[r][modd] - D[l][modd])        

if __name__=='__main__':
    main()

Fixed submission:
import sys
input = sys.stdin.readline
INF = 10 ** 9
MOD = 10 ** 9 + 7

def main(): 
    h,w,d = map(int,input().split())
    n = h * w

    idx = [0]*(1+n)
    for i in range(h):
        a = tuple(map(int,input().split()))
        for j in range(w):
            idx[a[j]] = (i + 1 , j + 1)
    idx[0] = idx[d]

    D = [0] * (n + 1)
    
    def dist(i,j):
        return abs(idx[i][0] - idx[j][0]) + abs(idx[i][1] - idx[j][1])
        
    for i in range(d):
        for j in range(i,n - d + 1,d):
            D[j + d] = D[j] + dist(j,j + d)
    
    q = int(input())
    for _ in range(q):
        l,r = map(int,input().split())
        print(D[r] - D[l])        

if __name__=='__main__':
    main()