Buggy python submission (verdict: Time Limit Exceeded):
import sys


class Square:
    def __init__(self, num, x, y):
        self.num = num
        self.x = x
        self.y = y
        self.adj = {self.num: 0}

    def merge(self, other):
        dist = abs(self.x - other.x) + abs(self.y - other.y)
        for k, m in other.adj.items():
            self.adj[k] = dist + m


def main():
    h, w, d = [int(x) for x in input().split()]
    dic = {}
    for i in range(h):
        line = [int(x) for x in input().split()]
        for j, a in enumerate(line):
            dic[a] = Square(a, i, j)
    for a in range(h*w, 0, -1):
        if a + d <= h*w:
            dic[a].merge(dic[a+d])
    q = int(input())
    for k in range(q):
        l, r = [int(x) for x in input().split()]
        print(dic[l].adj[r])


main()


Fixed submission:
import sys
import numpy as np


def main():
    h, w, d = [int(x) for x in input().split()]
    dic = {}
    for i in range(h):
        line = [int(x) for x in input().split()]
        for j, a in enumerate(line):
            dic[a] = (a, i, j)
    magic = [[0] for _ in range(d + 1)]
    for k in range(1, d + 1):
        for m in range(1, h * w):
            if k + (m * d) > h * w:
                break
            magic[k].append(magic[k][m - 1] +
                            abs(dic[k + (m * d)][1] - dic[k + ((m - 1) * d)][1]) +
                            abs(dic[k + (m * d)][2] - dic[k + ((m - 1) * d)][2]))
    q = int(input())
    for _ in range(q):
        l, r = [int(e) for e in input().split()]
        k = d if l % d == 0 else l % d
        print(magic[k][(r - 1) // d] - magic[k][(l - 1) // d])


main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np


class Square:
    def __init__(self, num, x, y):
        self.num = num
        self.x = x
        self.y = y
        self.adj = {self.num: 0}

    def merge(self, other):
        dist = abs(self.x - other.x) + abs(self.y - other.y)
        for k, m in other.adj.items():
            self.adj[k] = dist + m


def main():
    h, w, d = [int(x) for x in input().split()]
    dic = {}
    for i in range(h):
        line = [int(x) for x in input().split()]
        for j, a in enumerate(line):
            dic[a] = Square(a, i, j)
    for a in range(h*w, 0, -1):
        if a + d <= h*w:
            dic[a].merge(dic[a+d])
    q = int(input())
    for k in range(q):
        l, r = [int(x) for x in input().split()]
        print(dic[l].adj[r])


main()


Fixed submission:
import sys
import numpy as np


def main():
    h, w, d = [int(x) for x in input().split()]
    dic = {}
    for i in range(h):
        line = [int(x) for x in input().split()]
        for j, a in enumerate(line):
            dic[a] = (a, i, j)
    magic = [[0] for _ in range(d + 1)]
    for k in range(1, d + 1):
        for m in range(1, h * w):
            if k + (m * d) > h * w:
                break
            magic[k].append(magic[k][m - 1] +
                            abs(dic[k + (m * d)][1] - dic[k + ((m - 1) * d)][1]) +
                            abs(dic[k + (m * d)][2] - dic[k + ((m - 1) * d)][2]))
    q = int(input())
    for _ in range(q):
        l, r = [int(e) for e in input().split()]
        k = d if l % d == 0 else l % d
        print(magic[k][(r - 1) // d] - magic[k][(l - 1) // d])


main()