Buggy python submission (verdict: Time Limit Exceeded):
H,W,D = [int(n) for n in raw_input().split(" ")]
Location = {}
for h in range(1,H + 1):
	A = [int(n) for n in raw_input().split(" ")]
	for w, a in enumerate(A):
		Location[a] = (h, w+1)
Q = int(raw_input())
L = [None] * (Q+1)
R = [None] * (Q+1)
for q in range(1,Q+1):
	L[q], R[q] = [int(n) for n in raw_input().split(" ")]



C = {}
for q in range(1,Q+1):
	l, r = L[q], R[q]
	C[l,l] = 0
	C[r,r] = 0
	cur_dist = 0
	for x1 in range(l, r, D):
		x2 = x1 + D
		if (x1, r) in C:
			C[(l,r)] = C[l, x1] + C[(x1,r)]
			break
		elif (x1,x2) not in C:
			h1, w1 = Location[x1]
			h2, w2 = Location[x2]
			C[(x1, x2)] = abs(h1 - h2) + abs(w1 - w2)
		cur_dist = cur_dist + C[(x1,x2)]
		C[(l,x2)] = cur_dist
	print C[(l,r)]


Fixed submission:
H,W,D = [int(n) for n in raw_input().split(" ")]
Location = {}
for h in range(1,H + 1):
	A = [int(n) for n in raw_input().split(" ")]
	for w, a in enumerate(A):
		Location[a] = (h, w+1)
Q = int(raw_input())
L = [None] * (Q+1)
R = [None] * (Q+1)
for q in range(1,Q+1):
	L[q], R[q] = [int(n) for n in raw_input().split(" ")]



C = {}
for d in range(1,D+1):
	C[d,d] = 0
	cur_dist = 0
	for x1 in range(d, H * W + 1, D):
		x2 = x1 + D
		if x2 > H * W: 
			break
		h1, w1 = Location[x1]
		h2, w2 = Location[x2]
		#C[(x1, x2)] = abs(h1 - h2) + abs(w1 - w2)
		cur_dist = cur_dist + abs(h1 - h2) + abs(w1 - w2)
		C[(d,x2)] = cur_dist
	
for q in range(1,Q+1):
	l, r = L[q], R[q]
	d = l % D
	if d == 0: 
		d = D
	print (C[(d,r)] - C[(d,l)])

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D = [int(n) for n in raw_input().split(" ")]
A = [[None] * (W + 1)] * (H + 1)
Location = {}
for h in range(1,H + 1):
	A[h][1:W+1] = [int(n) for n in raw_input().split(" ")]
	for w, a in enumerate(A[h]):
		Location[a] = (h, w)
Q = int(raw_input())
L = [None] * (Q+1)
R = [None] * (Q+1)
for q in range(1,Q+1):
	L[q], R[q] = [int(n) for n in raw_input().split(" ")]



C = {}
for l in L:
	C[l,l] = 0
for q in range(1,Q+1):
	l = L[q]
	r = R[q]
	cur_dist = 0
	for x1 in range(l, r, D):
		x2 = x1 + D
		if (x1, r) in C:
			C[(l,r)] = C[l, x1] + C[(x1,r)]
			break
		if (x1,x2) not in C:
			h1, w1 = Location[x1]
			h2, w2 = Location[x2]
			C[(x1, x2)] = abs(h1 - h2) + abs(w1 - w2)
		cur_dist = cur_dist + C[(x1,x2)]
		C[(l,x2)] = cur_dist
	print C[(l,r)]

Fixed submission:
H,W,D = [int(n) for n in raw_input().split(" ")]
Location = {}
for h in range(1,H + 1):
	A = [int(n) for n in raw_input().split(" ")]
	for w, a in enumerate(A):
		Location[a] = (h, w+1)
Q = int(raw_input())
L = [None] * (Q+1)
R = [None] * (Q+1)
for q in range(1,Q+1):
	L[q], R[q] = [int(n) for n in raw_input().split(" ")]



C = {}
for d in range(1,D+1):
	C[d,d] = 0
	cur_dist = 0
	for x1 in range(d, H * W + 1, D):
		x2 = x1 + D
		if x2 > H * W: 
			break
		h1, w1 = Location[x1]
		h2, w2 = Location[x2]
		#C[(x1, x2)] = abs(h1 - h2) + abs(w1 - w2)
		cur_dist = cur_dist + abs(h1 - h2) + abs(w1 - w2)
		C[(d,x2)] = cur_dist
	
for q in range(1,Q+1):
	l, r = L[q], R[q]
	d = l % D
	if d == 0: 
		d = D
	print (C[(d,r)] - C[(d,l)])

Buggy python submission (verdict: Time Limit Exceeded):
H,W,D = [int(n) for n in raw_input().split(" ")]
A = [[None] * (W + 1)] * (H + 1)
Location = {}
for h in range(1,H + 1):
	A[h][1:W+1] = [int(n) for n in raw_input().split(" ")]
	for w, a in enumerate(A[h]):
		Location[a] = (h, w)
Q = int(raw_input())
L = [None] * (Q+1)
R = [None] * (Q+1)
for q in range(1,Q+1):
	L[q], R[q] = [int(n) for n in raw_input().split(" ")]



C = {}
for l in L:
	C[l,l] = 0
for q in range(1,Q+1):
	l = L[q]
	r = R[q]
	cur_dist = 0
	for x1 in range(l, r, D):
		x2 = x1 + D
		if (x1,x2) not in C:
			h1, w1 = Location[x1]
			h2, w2 = Location[x2]
			C[(x1, x2)] = abs(h1 - h2) + abs(w1 - w2)
		cur_dist = cur_dist + C[(x1,x2)]
		C[(l,x2)] = cur_dist
	print C[(l,r)]


Fixed submission:
H,W,D = [int(n) for n in raw_input().split(" ")]
Location = {}
for h in range(1,H + 1):
	A = [int(n) for n in raw_input().split(" ")]
	for w, a in enumerate(A):
		Location[a] = (h, w+1)
Q = int(raw_input())
L = [None] * (Q+1)
R = [None] * (Q+1)
for q in range(1,Q+1):
	L[q], R[q] = [int(n) for n in raw_input().split(" ")]



C = {}
for d in range(1,D+1):
	C[d,d] = 0
	cur_dist = 0
	for x1 in range(d, H * W + 1, D):
		x2 = x1 + D
		if x2 > H * W: 
			break
		h1, w1 = Location[x1]
		h2, w2 = Location[x2]
		#C[(x1, x2)] = abs(h1 - h2) + abs(w1 - w2)
		cur_dist = cur_dist + abs(h1 - h2) + abs(w1 - w2)
		C[(d,x2)] = cur_dist
	
for q in range(1,Q+1):
	l, r = L[q], R[q]
	d = l % D
	if d == 0: 
		d = D
	print (C[(d,r)] - C[(d,l)])