Buggy python submission (verdict: Time Limit Exceeded):
if __name__ == "__main__":
    H, W, D = list(map(int, (input().split(' '))))
    A = []
    for i in range(H):
        A.append(list(map(int, (input().split(' ')))))
    Q = int(input())
    LR = []
    for i in range(Q):
        LR.append(list(map(int, (input().split(' ')))))

    def check_val(H, W, A, target):
        for i in range(H):
            for j in range(W):
                if target == A[i][j]:
                    x = i
                    y = j
                    return x, y
        return -1, -1

#    check_list = []
#    for i in range(Q):
#        stat_LR = LR[i]
#        for j in range(stat_LR[0], stat_LR[1]+D, D):
#            check_list.append(j)
#    check_list = list(set(check_list))

#    buf = H * W
    dict_buf = {}
#    for i in check_list:
#        x, y = check_val(H, W, A, i)
#        if x != -1 and y != -1:
#            dict_buf[str(i)] = [x, y]
    for i in range(H):
        for j in range(W):
            dict_buf[str(A[i][j])] = [i, j]

    for i in range(Q):
        mp = 0
        stat_LR = LR[i]
        if stat_LR[0] == stat_LR[1]:
            print(mp)
            continue
        stat_x, stat_y = dict_buf[str(stat_LR[0])]
        next = stat_LR[0]
        while next != stat_LR[1]:
            next += D
            x, y = dict_buf[str(next)]
            mp += abs(x - stat_x) + abs(y - stat_y)
            stat_x = x
            stat_y = y
        print(mp)

Fixed submission:
if __name__ == "__main__":
    H, W, D = list(map(int, (input().split(' '))))
    A = []
    for i in range(H):
        A.append(list(map(int, (input().split(' ')))))
    Q = int(input())
    LR = []
    for i in range(Q):
        LR.append(list(map(int, (input().split(' ')))))

#    def check_val(H, W, A, target):
#        for i in range(H):
#            for j in range(W):
#                if target == A[i][j]:
#                    x = i
#                    y = j
#                    return x, y
#        return -1, -1

#    check_list = []
#    for i in range(Q):
#        stat_LR = LR[i]
#        for j in range(stat_LR[0], stat_LR[1]+D, D):
#            check_list.append(j)
#    check_list = list(set(check_list))

#    buf = H * W
    dict_buf = {}
#    for i in check_list:
#        x, y = check_val(H, W, A, i)
#        if x != -1 and y != -1:
#            dict_buf[str(i)] = [x, y]
    for i in range(H):
        for j in range(W):
            dict_buf[str(A[i][j])] = [i, j]

    d = {}
    for i in range(1, D+1):
        d[str(i)] = 0
    for i in range(D+1, H*W+1):
        d[str(i)] = d[str(i-D)] + \
                    abs(dict_buf[str(i)][0] - dict_buf[str(i-D)][0]) + \
                    abs(dict_buf[str(i)][1] - dict_buf[str(i-D)][1])

    for i in range(Q):
#        mp = 0
#        stat_LR = LR[i]
#        if stat_LR[0] == stat_LR[1]:
#            print(mp)
#            continue
#        stat_x, stat_y = dict_buf[str(stat_LR[0])]
#        next = stat_LR[0]
#        while next != stat_LR[1]:
#            next += D
#            x, y = dict_buf[str(next)]
#            mp += abs(x - stat_x) + abs(y - stat_y)
#            stat_x = x
#            stat_y = y
#        print(mp)
        print(d[str(LR[i][1])] - d[str(LR[i][0])])

Buggy python submission (verdict: Time Limit Exceeded):
if __name__ == "__main__":
    H, W, D = list(map(int, (input().split(' '))))
    A = []
    for i in range(H):
        A.append(list(map(int, (input().split(' ')))))
    Q = int(input())
    LR = []
    for i in range(Q):
        LR.append(list(map(int, (input().split(' ')))))

    def check_val(H, W, A, target):
        for i in range(H):
            for j in range(W):
                if target == A[i][j]:
                    x = i
                    y = j
                    return x, y
        return -1, -1

    check_list = []
    for i in range(Q):
        stat_LR = LR[i]
        for j in range(stat_LR[0], stat_LR[1]+D, D):
            check_list.append(j)
    check_list = list(set(check_list))

    buf = H * W
    dict_buf = {}
#    for i in check_list:
#        x, y = check_val(H, W, A, i)
#        if x != -1 and y != -1:
#            dict_buf[str(i)] = [x, y]
    for i in range(H):
        for j in range(W):
            dict_buf[str(A[i][j])] = [i, j]

    for i in range(Q):
        mp = 0
        stat_LR = LR[i]
        if stat_LR[0] == stat_LR[1]:
            print(mp)
            continue
        stat_x, stat_y = dict_buf[str(stat_LR[0])]
        next = stat_LR[0]
        while next != stat_LR[1]:
            next += D
            x, y = dict_buf[str(next)]
            mp += abs(x - stat_x) + abs(y - stat_y)
            stat_x = x
            stat_y = y
        print(mp)

Fixed submission:
if __name__ == "__main__":
    H, W, D = list(map(int, (input().split(' '))))
    A = []
    for i in range(H):
        A.append(list(map(int, (input().split(' ')))))
    Q = int(input())
    LR = []
    for i in range(Q):
        LR.append(list(map(int, (input().split(' ')))))

#    def check_val(H, W, A, target):
#        for i in range(H):
#            for j in range(W):
#                if target == A[i][j]:
#                    x = i
#                    y = j
#                    return x, y
#        return -1, -1

#    check_list = []
#    for i in range(Q):
#        stat_LR = LR[i]
#        for j in range(stat_LR[0], stat_LR[1]+D, D):
#            check_list.append(j)
#    check_list = list(set(check_list))

#    buf = H * W
    dict_buf = {}
#    for i in check_list:
#        x, y = check_val(H, W, A, i)
#        if x != -1 and y != -1:
#            dict_buf[str(i)] = [x, y]
    for i in range(H):
        for j in range(W):
            dict_buf[str(A[i][j])] = [i, j]

    d = {}
    for i in range(1, D+1):
        d[str(i)] = 0
    for i in range(D+1, H*W+1):
        d[str(i)] = d[str(i-D)] + \
                    abs(dict_buf[str(i)][0] - dict_buf[str(i-D)][0]) + \
                    abs(dict_buf[str(i)][1] - dict_buf[str(i-D)][1])

    for i in range(Q):
#        mp = 0
#        stat_LR = LR[i]
#        if stat_LR[0] == stat_LR[1]:
#            print(mp)
#            continue
#        stat_x, stat_y = dict_buf[str(stat_LR[0])]
#        next = stat_LR[0]
#        while next != stat_LR[1]:
#            next += D
#            x, y = dict_buf[str(next)]
#            mp += abs(x - stat_x) + abs(y - stat_y)
#            stat_x = x
#            stat_y = y
#        print(mp)
        print(d[str(LR[i][1])] - d[str(LR[i][0])])

Buggy python submission (verdict: Time Limit Exceeded):
if __name__ == "__main__":
    H, W, D = list(map(int, (input().split(' '))))
    A = []
    for i in range(H):
        A.append(list(map(int, (input().split(' ')))))
    Q = int(input())
    LR = []
    for i in range(Q):
        LR.append(list(map(int, (input().split(' ')))))

    def check_val(H, W, A, target):
        for i in range(H):
            for j in range(W):
                if target == A[i][j]:
                    x = i
                    y = j
                    return x, y
        return -1, -1

    check_list = []
    for i in range(Q):
        stat_LR = LR[i]
        for j in range(stat_LR[0], stat_LR[1]+D, D):
            check_list.append(j)
    check_list = list(set(check_list))

    buf = H * W
    dict_buf = {}
#    for i in range(1, buf+1):
    for i in check_list:
        x, y = check_val(H, W, A, i)
        if x != -1 and y != -1:
            dict_buf[str(i)] = [x, y]

    for i in range(Q):
        mp = 0
        stat_LR = LR[i]
        if stat_LR[0] == stat_LR[1]:
            print(mp)
            continue
#        stat_x, stat_y = check_val(H, W, A, stat_LR[0])
        stat_x, stat_y = dict_buf[str(stat_LR[0])]
        next = stat_LR[0]
        while next != stat_LR[1]:
            next += D
#            x, y = check_val(H, W, A, next)
            x, y = dict_buf[str(next)]
            mp += abs(x - stat_x) + abs(y - stat_y)
            stat_x = x
            stat_y = y
        print(mp)

Fixed submission:
if __name__ == "__main__":
    H, W, D = list(map(int, (input().split(' '))))
    A = []
    for i in range(H):
        A.append(list(map(int, (input().split(' ')))))
    Q = int(input())
    LR = []
    for i in range(Q):
        LR.append(list(map(int, (input().split(' ')))))

#    def check_val(H, W, A, target):
#        for i in range(H):
#            for j in range(W):
#                if target == A[i][j]:
#                    x = i
#                    y = j
#                    return x, y
#        return -1, -1

#    check_list = []
#    for i in range(Q):
#        stat_LR = LR[i]
#        for j in range(stat_LR[0], stat_LR[1]+D, D):
#            check_list.append(j)
#    check_list = list(set(check_list))

#    buf = H * W
    dict_buf = {}
#    for i in check_list:
#        x, y = check_val(H, W, A, i)
#        if x != -1 and y != -1:
#            dict_buf[str(i)] = [x, y]
    for i in range(H):
        for j in range(W):
            dict_buf[str(A[i][j])] = [i, j]

    d = {}
    for i in range(1, D+1):
        d[str(i)] = 0
    for i in range(D+1, H*W+1):
        d[str(i)] = d[str(i-D)] + \
                    abs(dict_buf[str(i)][0] - dict_buf[str(i-D)][0]) + \
                    abs(dict_buf[str(i)][1] - dict_buf[str(i-D)][1])

    for i in range(Q):
#        mp = 0
#        stat_LR = LR[i]
#        if stat_LR[0] == stat_LR[1]:
#            print(mp)
#            continue
#        stat_x, stat_y = dict_buf[str(stat_LR[0])]
#        next = stat_LR[0]
#        while next != stat_LR[1]:
#            next += D
#            x, y = dict_buf[str(next)]
#            mp += abs(x - stat_x) + abs(y - stat_y)
#            stat_x = x
#            stat_y = y
#        print(mp)
        print(d[str(LR[i][1])] - d[str(LR[i][0])])

Buggy python submission (verdict: Time Limit Exceeded):
if __name__ == "__main__":
    H, W, D = list(map(int, (input().split(' '))))
    A = []
    for i in range(H):
        A.append(list(map(int, (input().split(' ')))))
    Q = int(input())
    LR = []
    for i in range(Q):
        LR.append(list(map(int, (input().split(' ')))))

    def check_val(H, W, A, target):
        for i in range(H):
            for j in range(W):
                if target == A[i][j]:
                    x = i
                    y = j
                    return x, y
        return -1, -1

    buf = H * W
    dict_buf = {}
    for i in range(1, buf+1):
        x, y = check_val(H, W, A, i)
        if x != -1 and y != -1:
            dict_buf[str(i)] = [x, y]

    for i in range(Q):
        mp = 0
        stat_LR = LR[i]
        if stat_LR[0] == stat_LR[1]:
            print(mp)
            continue
#        stat_x, stat_y = check_val(H, W, A, stat_LR[0])
        stat_x, stat_y = dict_buf[str(stat_LR[0])]
        next = stat_LR[0]
        while next != stat_LR[1]:
            next += D
#            x, y = check_val(H, W, A, next)
            x, y = dict_buf[str(next)]
            mp += abs(x - stat_x) + abs(y - stat_y)
            stat_x = x
            stat_y = y
        print(mp)

Fixed submission:
if __name__ == "__main__":
    H, W, D = list(map(int, (input().split(' '))))
    A = []
    for i in range(H):
        A.append(list(map(int, (input().split(' ')))))
    Q = int(input())
    LR = []
    for i in range(Q):
        LR.append(list(map(int, (input().split(' ')))))

#    def check_val(H, W, A, target):
#        for i in range(H):
#            for j in range(W):
#                if target == A[i][j]:
#                    x = i
#                    y = j
#                    return x, y
#        return -1, -1

#    check_list = []
#    for i in range(Q):
#        stat_LR = LR[i]
#        for j in range(stat_LR[0], stat_LR[1]+D, D):
#            check_list.append(j)
#    check_list = list(set(check_list))

#    buf = H * W
    dict_buf = {}
#    for i in check_list:
#        x, y = check_val(H, W, A, i)
#        if x != -1 and y != -1:
#            dict_buf[str(i)] = [x, y]
    for i in range(H):
        for j in range(W):
            dict_buf[str(A[i][j])] = [i, j]

    d = {}
    for i in range(1, D+1):
        d[str(i)] = 0
    for i in range(D+1, H*W+1):
        d[str(i)] = d[str(i-D)] + \
                    abs(dict_buf[str(i)][0] - dict_buf[str(i-D)][0]) + \
                    abs(dict_buf[str(i)][1] - dict_buf[str(i-D)][1])

    for i in range(Q):
#        mp = 0
#        stat_LR = LR[i]
#        if stat_LR[0] == stat_LR[1]:
#            print(mp)
#            continue
#        stat_x, stat_y = dict_buf[str(stat_LR[0])]
#        next = stat_LR[0]
#        while next != stat_LR[1]:
#            next += D
#            x, y = dict_buf[str(next)]
#            mp += abs(x - stat_x) + abs(y - stat_y)
#            stat_x = x
#            stat_y = y
#        print(mp)
        print(d[str(LR[i][1])] - d[str(LR[i][0])])

Buggy python submission (verdict: Time Limit Exceeded):
if __name__ == "__main__":
    H, W, D = list(map(int, (input().split(' '))))
    A = []
    for i in range(H):
        A.append(list(map(int, (input().split(' ')))))
    Q = int(input())
    LR = []
    for i in range(Q):
        LR.append(list(map(int, (input().split(' ')))))

    def check_val(H, W, A, target):
        for i in range(H):
            for j in range(W):
                if target == A[i][j]:
                    x = i
                    y = j
                    return x, y
        return 0, 0

    for i in range(Q):
        mp = 0
        stat_LR = LR[i]
        if stat_LR[0] == stat_LR[1]:
            print(mp)
            continue
        stat_x, stat_y = check_val(H, W, A, stat_LR[0])
        next = stat_LR[0]
        while next != stat_LR[1]:
            next += D
            x, y = check_val(H, W, A, next)
            mp += abs(x - stat_x) + abs(y - stat_y)
            stat_x = x
            stat_y = y
        print(mp)

Fixed submission:
if __name__ == "__main__":
    H, W, D = list(map(int, (input().split(' '))))
    A = []
    for i in range(H):
        A.append(list(map(int, (input().split(' ')))))
    Q = int(input())
    LR = []
    for i in range(Q):
        LR.append(list(map(int, (input().split(' ')))))

#    def check_val(H, W, A, target):
#        for i in range(H):
#            for j in range(W):
#                if target == A[i][j]:
#                    x = i
#                    y = j
#                    return x, y
#        return -1, -1

#    check_list = []
#    for i in range(Q):
#        stat_LR = LR[i]
#        for j in range(stat_LR[0], stat_LR[1]+D, D):
#            check_list.append(j)
#    check_list = list(set(check_list))

#    buf = H * W
    dict_buf = {}
#    for i in check_list:
#        x, y = check_val(H, W, A, i)
#        if x != -1 and y != -1:
#            dict_buf[str(i)] = [x, y]
    for i in range(H):
        for j in range(W):
            dict_buf[str(A[i][j])] = [i, j]

    d = {}
    for i in range(1, D+1):
        d[str(i)] = 0
    for i in range(D+1, H*W+1):
        d[str(i)] = d[str(i-D)] + \
                    abs(dict_buf[str(i)][0] - dict_buf[str(i-D)][0]) + \
                    abs(dict_buf[str(i)][1] - dict_buf[str(i-D)][1])

    for i in range(Q):
#        mp = 0
#        stat_LR = LR[i]
#        if stat_LR[0] == stat_LR[1]:
#            print(mp)
#            continue
#        stat_x, stat_y = dict_buf[str(stat_LR[0])]
#        next = stat_LR[0]
#        while next != stat_LR[1]:
#            next += D
#            x, y = dict_buf[str(next)]
#            mp += abs(x - stat_x) + abs(y - stat_y)
#            stat_x = x
#            stat_y = y
#        print(mp)
        print(d[str(LR[i][1])] - d[str(LR[i][0])])