Buggy python submission (verdict: Time Limit Exceeded):
h, w, d = map(int, input().split())
X = [None for k in range(h*w)]
for i in range(h):
    *A, = map(int, input().split())
    for j in range(w):
        X[A[j]-1] = (i, j)
D = []
for k in range(h*w):
    if k+d < h*w:
        x0, y0 = X[k]
        x1, y1 = X[k+d]
        D.append(abs(x0-x1)+abs(y0-y1))
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    ans = 0
    for k in range(l-1, r-1, d):
        ans += D[k]
    print(ans)


Fixed submission:
h, w, d = map(int, input().split())
X = [None for k in range(h*w)]
for i in range(h):
    *A, = map(int, input().split())
    for j in range(w):
        X[A[j]-1] = (i, j)
D = []
for k in range(h*w):
    if k < d:
        D.append(0)
    else:
        x0, y0 = X[k]
        x1, y1 = X[k-d]
        D.append(D[k-d]+abs(x0-x1)+abs(y0-y1))
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(D[r-1]-D[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque


def bfs(G, a, b):
    # グラフGにおいてaからbへの距離
    # 到達不可能な場合は-1を返す
    n = len(G)
    d = [-1] * n
    que = deque([a])
    d[a] = 0
    while que:
        x = que.popleft()
        if x == b:
            return d[b]
        next = G[x]
        for y in next:
            if d[y] == -1:
                que.append(y)
                d[y] = d[x] + 1
    return d[b]


h, w, d = map(int, input().split())
A = [list(map(int, input().split())) for i in range(h)]
G = [[] for k in range(h*w)]
for i in range(h):
    for j in range(w):
        if i > 0:
            G[A[i][j]-1].append(A[i-1][j]-1)
        if i < h-1:
            G[A[i][j]-1].append(A[i+1][j]-1)
        if j > 0:
            G[A[i][j]-1].append(A[i][j-1]-1)
        if j < w-1:
            G[A[i][j]-1].append(A[i][j+1]-1)
D = []
for k in range(h*w):
    if k+d < h*w:
        D.append(bfs(G, k, k+d))

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    x = 0
    for k in range(l-1, r-1, d):
        x += D[k]
    print(x)


Fixed submission:
h, w, d = map(int, input().split())
X = [None for k in range(h*w)]
for i in range(h):
    *A, = map(int, input().split())
    for j in range(w):
        X[A[j]-1] = (i, j)
D = []
for k in range(h*w):
    if k < d:
        D.append(0)
    else:
        x0, y0 = X[k]
        x1, y1 = X[k-d]
        D.append(D[k-d]+abs(x0-x1)+abs(y0-y1))
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(D[r-1]-D[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque


def bfs(G, a, b):
    # グラフGにおいてaからbへの距離
    # 到達不可能な場合は-1を返す
    n = len(G)
    d = [-1] * n
    que = deque([a])
    d[a] = 0
    while que:
        x = que.popleft()
        if x == b:
            return d[b]
        next = G[x]
        for y in next:
            if d[y] == -1:
                que.append(y)
                d[y] = d[x] + 1
    return d[b]


h, w, d = map(int, input().split())
A = [list(map(int, input().split())) for i in range(h)]
G = [[] for k in range(h*w)]
for i in range(h):
    for j in range(w):
        if i > 0:
            G[A[i][j]-1].append(A[i-1][j]-1)
        if i < h-1:
            G[A[i][j]-1].append(A[i+1][j]-1)
        if j > 0:
            G[A[i][j]-1].append(A[i][j-1]-1)
        if j < w-1:
            G[A[i][j]-1].append(A[i][j+1]-1)
D = []
for k in range(h*w):
    if k+d < h*w:
        D.append(bfs(G, k, k+d))

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    x = 0
    for k in range(l-1, r-1, d):
        x += D[k]
    print(x)


Fixed submission:
h, w, d = map(int, input().split())
X = [None for k in range(h*w)]
for i in range(h):
    *A, = map(int, input().split())
    for j in range(w):
        X[A[j]-1] = (i, j)
D = []
for k in range(h*w):
    if k < d:
        D.append(0)
    else:
        x0, y0 = X[k]
        x1, y1 = X[k-d]
        D.append(D[k-d]+abs(x0-x1)+abs(y0-y1))
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(D[r-1]-D[l-1])

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


def INDEX(x):
    for i in range(H):
        if x in A[i]:
            for j in range(W):
                if x==A[i][j]:
                    return((i,j))
                
for q in LR:
    start=q[0]
    goal=q[1]
    distance=0
    while start!=goal:
        distance+=abs(INDEX(start)[0]-INDEX(start+D)[0])+abs(INDEX(start)[1]-INDEX(start+D)[1])
        start=start+D
    print(distance)

Fixed submission:
h, w, d = map(int, input().split())
X = [None for k in range(h*w)]
for i in range(h):
    *A, = map(int, input().split())
    for j in range(w):
        X[A[j]-1] = (i, j)
D = []
for k in range(h*w):
    if k < d:
        D.append(0)
    else:
        x0, y0 = X[k]
        x1, y1 = X[k-d]
        D.append(D[k-d]+abs(x0-x1)+abs(y0-y1))
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(D[r-1]-D[l-1])