Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

h, w, d = [ int(v) for v in input().split() ]
def manhattan(intuple1,intuple2):
	return abs(intuple1[2]-intuple2[2]) + abs(intuple1[1]-intuple2[1])

grid_list = [ None for i in range(w*h) ]
for i in range(h):
	num_list = [ int(v) for v in input().split() ]
	for j in range(w):
		grid_list[i*w+j] = (num_list[j],i,j)
grid_list = sorted(grid_list)


m = int(input())
for i in range(m):
	l, r = [ int(v) for v in input().split() ]
	score = 0
	left = grid_list[l-1]
	for j in range(l+d,r+d,d):
		right = grid_list[j-1]
		score += manhattan(left,right)
		left = right
	print(score)

Fixed submission:
import sys
input = sys.stdin.readline

h, w, d = [ int(v) for v in input().split() ]
def manhattan(intuple1,intuple2):
	return abs(intuple1[2]-intuple2[2]) + abs(intuple1[1]-intuple2[1])

grid_list = [ None for i in range(w*h) ]
for i in range(h):
	num_list = [ int(v) for v in input().split() ]
	for j in range(w):
		grid_list[i*w+j] = (num_list[j],i,j)
grid_list = sorted(grid_list)

sum_list = []

for i in range(1,d+1):
	temp_list = []
	left = i
	s = 0
	for j in range(i,w*h+1,d):
		s +=  manhattan(grid_list[left-1],grid_list[j-1])
		temp_list.append(s)

		left = j
	sum_list.append(temp_list)

m = int(input())
for i in range(m):
	l, r = [ int(v) for v in input().split() ]
	print(sum_list[r%d-1][(r-1)//d]-sum_list[l%d-1][(l-1)//d])

Buggy python submission (verdict: Time Limit Exceeded):
h, w, d = [ int(v) for v in input().split() ]
def manhattan(intuple1,intuple2):
	return abs(intuple1[2]-intuple2[2]) + abs(intuple1[1]-intuple2[1])

grid_list = [ None for i in range(w*h) ]
for i in range(h):
	num_list = [ int(v) for v in input().split() ]
	for j in range(w):
		grid_list[i*w+j] = (num_list[j],i,j)
grid_list = sorted(grid_list)


m = int(input())
for i in range(m):
	l, r = [ int(v) for v in input().split() ]
	score = 0
	left = grid_list[l-1]
	for j in range(l+d,r+d,d):
		right = grid_list[j-1]
		score += manhattan(left,right)
		left = right
	print(score)

Fixed submission:
import sys
input = sys.stdin.readline

h, w, d = [ int(v) for v in input().split() ]
def manhattan(intuple1,intuple2):
	return abs(intuple1[2]-intuple2[2]) + abs(intuple1[1]-intuple2[1])

grid_list = [ None for i in range(w*h) ]
for i in range(h):
	num_list = [ int(v) for v in input().split() ]
	for j in range(w):
		grid_list[i*w+j] = (num_list[j],i,j)
grid_list = sorted(grid_list)

sum_list = []

for i in range(1,d+1):
	temp_list = []
	left = i
	s = 0
	for j in range(i,w*h+1,d):
		s +=  manhattan(grid_list[left-1],grid_list[j-1])
		temp_list.append(s)

		left = j
	sum_list.append(temp_list)

m = int(input())
for i in range(m):
	l, r = [ int(v) for v in input().split() ]
	print(sum_list[r%d-1][(r-1)//d]-sum_list[l%d-1][(l-1)//d])

Buggy python submission (verdict: Runtime Error):
h, w, d = [ int(v) for v in input().split() ]
def manhattan(intuple1,intuple2):
	return abs(intuple1[2]-intuple2[2]) + abs(intuple1[1]-intuple2[1])

grid_list = [ None for i in range(w*h) ]
for i in range(h):
	num_list = [ int(v) for v in input().split() ]
	for j in range(w):
		grid_list[i*h+j] = (num_list[j],i,j)
grid_list = sorted(grid_list)


m = int(input())
for i in range(m):
	l, r = [ int(v) for v in input().split() ]
	score = 0
	left = grid_list[l-1]
	for j in range(l+d,r+d,d):
		right = grid_list[j-1]
		score += manhattan(left,right)
		left = right
	print(score)


Fixed submission:
import sys
input = sys.stdin.readline

h, w, d = [ int(v) for v in input().split() ]
def manhattan(intuple1,intuple2):
	return abs(intuple1[2]-intuple2[2]) + abs(intuple1[1]-intuple2[1])

grid_list = [ None for i in range(w*h) ]
for i in range(h):
	num_list = [ int(v) for v in input().split() ]
	for j in range(w):
		grid_list[i*w+j] = (num_list[j],i,j)
grid_list = sorted(grid_list)

sum_list = []

for i in range(1,d+1):
	temp_list = []
	left = i
	s = 0
	for j in range(i,w*h+1,d):
		s +=  manhattan(grid_list[left-1],grid_list[j-1])
		temp_list.append(s)

		left = j
	sum_list.append(temp_list)

m = int(input())
for i in range(m):
	l, r = [ int(v) for v in input().split() ]
	print(sum_list[r%d-1][(r-1)//d]-sum_list[l%d-1][(l-1)//d])