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

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1

def main():
    h, w, d = map(int, input().split())
    atoij = [[] for _ in range(h * w)]
    for i in range(h):
        for j, a in enumerate(map(int, input().split())):
            a -= 1
            atoij[a] = [i, j]
    # print(atoij)
    q = int(input())
    for _ in range(q):
        l, r = map(int1, input().split())
        ans = 0
        i0, j0 = atoij[l]
        while l < r:
            l += d
            i1, j1 = atoij[l]
            ans += abs(i0 - i1) + abs(j0 - j1)
            i0, j0 = i1, j1
        print(ans)

main()


Fixed submission:
# TLE
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1

def main():
    h, w, d = map(int, input().split())
    atoij = [[] for _ in range(h * w)]
    for i in range(h):
        for j, a in enumerate(map(int, input().split())):
            a -= 1
            atoij[a] = [i, j]
    # print(atoij)
    q = int(input())
    ans=[0]*q
    mx = [0] * d
    mn = [100000] * d
    qq = [[] for _ in range(d)]
    for qi in range(q):
        l, r = map(int1, input().split())
        md = l % d
        if l < mn[md]: mn[md] = l
        if r > mx[md]: mx[md] = r
        qq[md].append([qi, l, r])
    for md in range(d):
        if not qq[md]: continue
        a = mn[md]
        ed = mx[md]
        s = 0
        dist = {}
        i0, j0 = atoij[a]
        while a <= ed:
            i1, j1 = atoij[a]
            s += abs(i0 - i1) + abs(j0 - j1)
            dist[a] = s
            i0, j0 = i1, j1
            a += d
        for qi, l, r in qq[md]:
            ans[qi]=dist[r]-dist[l]
    for x in ans:
        print(x)

main()

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

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1

def main():
    h, w, d = map(int, input().split())
    atoij = [[] for _ in range(h * w)]
    for i in range(h):
        for j, a in enumerate(map(int, input().split())):
            a -= 1
            atoij[a] = [i, j]
    # print(atoij)
    q = int(input())
    for _ in range(q):
        l, r = map(int1, input().split())
        ans = 0
        i0, j0 = atoij[l]
        while l < r:
            l += d
            i1, j1 = atoij[l]
            ans += abs(i0 - i1) + abs(j0 - j1)
            i0, j0 = i1, j1
        print(ans)

main()


Fixed submission:
# TLE
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1

def main():
    h, w, d = map(int, input().split())
    atoij = [[] for _ in range(h * w)]
    for i in range(h):
        for j, a in enumerate(map(int, input().split())):
            a -= 1
            atoij[a] = [i, j]
    # print(atoij)
    q = int(input())
    ans=[0]*q
    mx = [0] * d
    mn = [100000] * d
    qq = [[] for _ in range(d)]
    for qi in range(q):
        l, r = map(int1, input().split())
        md = l % d
        if l < mn[md]: mn[md] = l
        if r > mx[md]: mx[md] = r
        qq[md].append([qi, l, r])
    for md in range(d):
        if not qq[md]: continue
        a = mn[md]
        ed = mx[md]
        s = 0
        dist = {}
        i0, j0 = atoij[a]
        while a <= ed:
            i1, j1 = atoij[a]
            s += abs(i0 - i1) + abs(j0 - j1)
            dist[a] = s
            i0, j0 = i1, j1
            a += d
        for qi, l, r in qq[md]:
            ans[qi]=dist[r]-dist[l]
    for x in ans:
        print(x)

main()