Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
import numpy as np
# from itertools import accumulate
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H,W,D = map(int,readline().split())
N = H*W
ind = [0]*N
d = {}

A = []
for _ in range(H):
    row = list(map(int,readline().split()))
    A += row
    
for i in range(1,N+1):
    ind = A.index(i)
    x = ind // W
    y = ind % W
    d[i] = (x+1,y+1)
# print(d)

data = [[] for i in range(D)]
ac_data = []
for i in range(1,D+1):
    n = 1
    while i + D*n <= N: 
        x,y = d[i+D*(n-1)]
        nx,ny = d[i+D*n]
        power = abs(x-nx) + abs(y-ny)
        data[i%D].append(power)
        n += 1
# print(data)      
for row in data:
    row = [0] +row
    # ac_row = list(accumulate(row))
    ac_row = np.cumsum(row)
    ac_data.append(ac_row)

# print(ac_data)
Q = int(readline())
for i in range(Q):
    L,R = map(int,readline().split())
    k = L % D
    l = L // D 
    m = (R-L) // D
    if k == 0:
        print(ac_data[k][l-1+m]-ac_data[k][l-1])
    else:
        print(ac_data[k][l+m]-ac_data[k][l])

Fixed submission:
# -*- coding: utf-8 -*-
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H,W,D = map(int,readline().split())
X = [(0,0) for _ in range(H*W)]
Y = [0 for _ in range(H*W)]

for i in range(H):
    A = [int(x)-1 for x in readline().split()]
    for j in range(W):
        X[A[j]] = (i,j)

for i in range(0,H*W-D):
    Y[i+D] = Y[i] + abs(X[i+D][0] - X[i][0]) + abs(X[i+D][1] - X[i][1])

Q = int(readline())
for _ in range(Q):
    L,R = map(int,readline().split())
    print(Y[R-1]-Y[L-1])

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
import sys
from itertools import accumulate
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H,W,D = map(int,readline().split())
N = H*W
ind = [0]*N
d = {}

A = []
for _ in range(H):
    row = list(map(int,readline().split()))
    A += row
    
for i in range(1,N+1):
    ind = A.index(i)
    x = ind // W
    y = ind % W
    d[i] = (x+1,y+1)
# print(d)

data = [[] for i in range(D)]
ac_data = []
for i in range(1,D+1):
    n = 1
    while i + D*n <= N: 
        x,y = d[i+D*(n-1)]
        nx,ny = d[i+D*n]
        power = abs(x-nx) + abs(y-ny)
        data[i%D].append(power)
        n += 1
# print(data)      
for row in data:
    row = [0] +row
    ac_row = list(accumulate(row))
    ac_data.append(ac_row)

# print(ac_data)
Q = int(readline())
for i in range(Q):
    L,R = map(int,readline().split())
    k = L % D
    l = L // D 
    m = (R-L) // D
    if k == 0:
        print(ac_data[k][l-1+m]-ac_data[k][l-1])
    else:
        print(ac_data[k][l+m]-ac_data[k][l])

Fixed submission:
# -*- coding: utf-8 -*-
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
H,W,D = map(int,readline().split())
X = [(0,0) for _ in range(H*W)]
Y = [0 for _ in range(H*W)]

for i in range(H):
    A = [int(x)-1 for x in readline().split()]
    for j in range(W):
        X[A[j]] = (i,j)

for i in range(0,H*W-D):
    Y[i+D] = Y[i] + abs(X[i+D][0] - X[i][0]) + abs(X[i+D][1] - X[i][1])

Q = int(readline())
for _ in range(Q):
    L,R = map(int,readline().split())
    print(Y[R-1]-Y[L-1])