Buggy python submission (verdict: Time Limit Exceeded):
H, W, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(H)]

place = [[0, 0] for _ in range(H * W)]
for h in range(H):
	for w in range(W):
		place[a[h][w] - 1] = [h, w]

cost = [abs(place[i][0] - place[i + d][0]) + abs(place[i][1] - place[i + d][1]) for i in range(H * W - d)]

ans = [[0 for _ in range(H * W)] for _ in range(H * W)]

for i in range(H * W):
	for j in range(i, H * W, d):
		num = 0
		for k in range(i, j, d):
			num += cost[k]
		ans[i][j] = num

Q = int(input())

for q in range(Q):
	l, r = map(int, input().split())
	print(ans[l-1][r-1])

Fixed submission:
H, W, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(H)]

place = [[0, 0] for _ in range(H * W)]
for h in range(H):
	for w in range(W):
		place[a[h][w] - 1] = [h, w]

cost = [abs(place[i][0] - place[i + d][0]) + abs(place[i][1] - place[i + d][1]) for i in range(H * W - d)]

ans = [0 for _ in range(H * W)]

for i in range(d, H * W):
	ans[i] = ans[i - d] + cost[i - d]

Q = int(input())

for q in range(Q):
	l, r = map(int, input().split())
	print(ans[r - 1] - ans[l - 1])

Buggy python submission (verdict: Time Limit Exceeded):
H, W, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(H)]

place = [[0, 0] for _ in range(H * W)]
for h in range(H):
	for w in range(W):
		place[a[h][w] - 1] = [h, w]

cost = [abs(place[i][0] - place[i + d][0]) + abs(place[i][1] - place[i + d][1]) for i in range(H * W - d)]

ans = [[0 for _ in range(H * W)] for _ in range(H * W)]

for i in range(H * W):
	for j in range(i, H * W, d):
		num = 0
		for k in range(i, j, d):
			num += cost[k]
		ans[i][j] = num

Q = int(input())

for q in range(Q):
	l, r = map(int, input().split())
	print(ans[l-1][r-1])

Fixed submission:
H, W, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(H)]

place = [[0, 0] for _ in range(H * W)]
for h in range(H):
	for w in range(W):
		place[a[h][w] - 1] = [h, w]

cost = [abs(place[i][0] - place[i + d][0]) + abs(place[i][1] - place[i + d][1]) for i in range(H * W - d)]

ans = [0 for _ in range(H * W)]

for i in range(d, H * W):
	ans[i] = ans[i - d] + cost[i - d]

Q = int(input())

for q in range(Q):
	l, r = map(int, input().split())
	print(ans[r - 1] - ans[l - 1])

Buggy python submission (verdict: Time Limit Exceeded):
H, W, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(H)]

place = [[0, 0] for _ in range(H * W)]
for h in range(H):
	for w in range(W):
		place[a[h][w] - 1] = [h, w]

cost = [abs(place[i][0] - place[i + d][0]) + abs(place[i][1] - place[i + d][1]) for i in range(H * W - d)]

Q = int(input())

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

Fixed submission:
H, W, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(H)]

place = [[0, 0] for _ in range(H * W)]
for h in range(H):
	for w in range(W):
		place[a[h][w] - 1] = [h, w]

cost = [abs(place[i][0] - place[i + d][0]) + abs(place[i][1] - place[i + d][1]) for i in range(H * W - d)]

ans = [0 for _ in range(H * W)]

for i in range(d, H * W):
	ans[i] = ans[i - d] + cost[i - d]

Q = int(input())

for q in range(Q):
	l, r = map(int, input().split())
	print(ans[r - 1] - ans[l - 1])

Buggy python submission (verdict: Time Limit Exceeded):
H, W, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(H)]

place = [[0, 0] for _ in range(H * W)]
for h in range(H):
	for w in range(W):
		place[a[h][w] - 1] = [h, w]

cost = [abs(place[i][0] - place[i + d][0]) + abs(place[i][1] - place[i + d][1]) for i in range(H * W - d)]

Q = int(input())

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

Fixed submission:
H, W, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(H)]

place = [[0, 0] for _ in range(H * W)]
for h in range(H):
	for w in range(W):
		place[a[h][w] - 1] = [h, w]

cost = [abs(place[i][0] - place[i + d][0]) + abs(place[i][1] - place[i + d][1]) for i in range(H * W - d)]

ans = [0 for _ in range(H * W)]

for i in range(d, H * W):
	ans[i] = ans[i - d] + cost[i - d]

Q = int(input())

for q in range(Q):
	l, r = map(int, input().split())
	print(ans[r - 1] - ans[l - 1])