AtCoder Beginner Contest 089 - Practical Skill Test

We have a grid with H rows and W columns. The square at the i-th row and the j-th column will be called Square (i,j).
The integers from 1 through H×W are written throughout the grid, and the integer written in Square (i,j) is A_{i,j}.
You, a magical girl, can teleport a piece placed on Square (i,j) to Square (x,y) by consuming |x-i|+|y-j| magic points.
You now have to take Q practical tests of your ability as a magical girl.
The i-th test will be conducted as follows:
 - Initially, a piece is placed on the square where the integer L_i is written.
 - Let x be the integer written in the square occupied by the piece. Repeatedly move the piece to the square where the integer x+D is written, as long as x is not R_i. The test ends when x=R_i.
 - Here, it is guaranteed that R_i-L_i is a multiple of D.
For each test, find the sum of magic points consumed during that test.

-----Constraints-----
 - 1 \leq H,W \leq 300
 - 1 \leq D \leq H×W
 - 1 \leq A_{i,j} \leq H×W
 - A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))
 - 1 \leq Q \leq 10^5
 - 1 \leq L_i \leq R_i \leq H×W
 - (R_i-L_i) is a multiple of D.

-----Input-----
Input is given from Standard Input in the following format:
H W D
A_{1,1} A_{1,2} ... A_{1,W}
:
A_{H,1} A_{H,2} ... A_{H,W}
Q
L_1 R_1
:
L_Q R_Q

-----Output-----
For each test, print the sum of magic points consumed during that test.
Output should be in the order the tests are conducted.

-----Sample Input-----
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8

-----Sample Output-----
5

 - 4 is written in Square (1,2).
 - 6 is written in Square (3,3).
 - 8 is written in Square (3,1).
Thus, the sum of magic points consumed during the first test is (|3-1|+|3-2|)+(|3-3|+|1-3|)=5.

Difficulty: MEDIUM

Starter code:

Solutions:
(H, W, D) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(H)]
Q = int(input())
y = [[-1, -1] for i in range(H * W + 1)]
for i in range(H):
	for j in range(W):
		y[a[i][j]] = [i, j]
x = [0 for i in range(H * W + 1)]
for i in range(D + 1, H * W + 1):
	x[i] = x[i - D] + abs(y[i][0] - y[i - D][0]) + abs(y[i][1] - y[i - D][1])
for q in range(Q):
	(L, R) = map(int, input().split())
	print(x[R] - x[L])


import sys
input = sys.stdin.readline
(h, w, d) = map(int, input().split())
n = h * w
place = [0] * n
for i in range(h):
	a = [int(x) for x in input().split()]
	for j in range(w):
		place[a[j] - 1] = (i, j)
bit = [0] * n
for i in range(n):
	if i < d:
		continue
	bit[i] = bit[i - d] + abs(place[i][0] - place[i - d][0]) + abs(place[i][1] - place[i - d][1])
q = int(input())
for i in range(q):
	(l, r) = map(int, input().split())
	print(bit[r - 1] - bit[l - 1])


(H, W, D) = map(int, input().split())
X = [(0, 0) for _ in range(H * W)]
Y = [0] * (H * W)
for i in range(H):
	A = [int(a) - 1 for a in input().split()]
	for j in range(W):
		X[A[j]] = (i, j)
for i in range(H * W - D):
	Y[i + D] = Y[i] + abs(X[i + D][0] - X[i][0]) + abs(X[i + D][1] - X[i][1])
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(Y[r - 1] - Y[l - 1])


I = lambda : map(int, input().split())
(h, w, d) = I()
H = {}
W = {}
for i in range(1, h + 1):
	for (j, k) in enumerate(I(), 1):
		(H[k], W[k]) = (i, j)
x = 1 + h * w
s = [0 for _ in [0] * x]
for i in range(d + 1, x):
	s[i] = s[i - d] + abs(H[i] - H[i - d]) + abs(W[i] - W[i - d])
for _ in [0] * int(input()):
	(a, b) = I()
	print(s[b] - s[a])


(h, w, D) = map(int, input().split())
a = [[int(i) for i in input().split()] for _ in range(h)]
px = [0] * (h * w + 1)
py = [0] * (h * w + 1)
d = [0] * (h * w + 1)
for i in range(h):
	for j in range(w):
		px[a[i][j]] = i
		py[a[i][j]] = j
for i in range(D + 1, h * w + 1):
	d[i] = d[i - D] + abs(px[i] - px[i - D]) + abs(py[i] - py[i - D])
q = int(input())
for _ in range(q):
	(l, r) = map(int, input().split())
	print(d[r] - d[l])


(H, W, D) = map(int, input().split())
P = [None] * (H * W + 1)
for h in range(H):
	A = list(map(int, input().split()))
	for w in range(W):
		P[A[w]] = [h, w]
B = [0] * (H * W + 1)
for n in range(D + 1, H * W + 1):
	B[n] = B[n - D] + abs(P[n][0] - P[n - D][0]) + abs(P[n][1] - P[n - D][1])
Q = int(input())
ans = 0
for q in range(Q):
	(L, R) = map(int, input().split())
	print(B[R] - B[L])


(h, w, d) = list(map(int, input().split()))
aa = [list(map(int, input().split())) for _ in range(h)]
cd = [None] * (h * w)
for y in range(h):
	for x in range(w):
		cd[aa[y][x] - 1] = (x, y)
sc = [None] * (h * w)
sc[:d] = [0] * d
for i in range(d, h * w):
	sc[i] = sc[i - d] + abs(cd[i][0] - cd[i - d][0]) + abs(cd[i][1] - cd[i - d][1])
q = int(input())
for i in range(q):
	(l, r) = [int(x) - 1 for x in input().split()]
	print(sc[r] - sc[l])


import sys
import math
import collections
import bisect
import itertools
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
ni = lambda : int(sys.stdin.readline().rstrip())
ns = lambda : list(map(int, sys.stdin.readline().rstrip().split()))
na = lambda : list(map(int, sys.stdin.readline().rstrip().split()))
na1 = lambda : list([int(x) - 1 for x in sys.stdin.readline().rstrip().split()])

def main():
	(h, w, d) = ns()
	pos = dict()
	for i in range(h):
		a = na()
		for (j, ai) in enumerate(a):
			pos[ai - 1] = (i, j)
	cum = [[0] for _ in range(d)]
	for i in range(d):
		(x, y) = pos[i]
		num = i
		while num + d < h * w:
			num += d
			(xi, yi) = pos[num]
			tmp = abs(xi - x) + abs(yi - y)
			cum[i].append(cum[i][-1] + tmp)
			(x, y) = (xi, yi)
	q = ni()
	for _ in range(q):
		(l, r) = ns()
		(l, r) = (l - 1, r - 1)
		tmp = cum[l % d][r // d] - cum[l % d][l // d]
		print(tmp)

def __starting_point():
	main()
__starting_point()


import sys

def Is():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())
(H, W, D) = Is()
d = dict()
for i in range(H):
	s = Is()
	for (j, e) in enumerate(s):
		d[e] = (i, j)
m = [0] * (H * W + 1)
for i in range(D + 1, H * W + 1):
	m[i] = m[i - D] + abs(d[i - D][0] - d[i][0]) + abs(d[i - D][1] - d[i][1])
Q = I()
for q in range(Q):
	(l, r) = Is()
	print(m[r] - m[l])


(H, W, D) = map(int, input().split())
Point = {}
for y in range(H):
	line = list(map(int, input().split()))
	for (x, p) in enumerate(line):
		Point[p] = (y, x)
Q = int(input())

def dist(ny, nx, py, px):
	return abs(ny - py) + abs(nx - px)
Cost = [0] * (H * W + 1)
for i in range(D + 1, H * W + 1):
	(yi, xi) = Point[i - D]
	(yj, xj) = Point[i]
	Cost[i] = Cost[i - D] + dist(yi, xi, yj, xj)
for i in range(Q):
	(l, r) = map(int, input().split())
	print(Cost[r] - Cost[l])


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))

def ZIP(n):
	return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
(H, W, D) = MAP()
A = [LIST() for _ in range(H)]
dic = defaultdict(tuple)
for y in range(H):
	for x in range(W):
		dic[A[y][x]] = (y + 1, x + 1)
power = [[] for _ in range(D)]
for i in range(1, H * W + 1):
	if i <= D:
		power[i % D].append(0)
	else:
		idx = i % D
		tmp = abs(dic[i][0] - dic[i - D][0]) + abs(dic[i][1] - dic[i - D][1])
		power[i % D].append(tmp)
power_acc = []
for x in power:
	power_acc.append(list(accumulate(x)))
Q = INT()
for _ in range(Q):
	(L, R) = MAP()
	if L % D:
		print(power_acc[R % D][R // D] - power_acc[L % D][L // D])
	else:
		print(power_acc[R % D][R // D - 1] - power_acc[L % D][L // D - 1])


import sys
import math
from collections import deque
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda : sys.stdin.readline().strip()
NI = lambda : int(input())
NMI = lambda : map(int, input().split())
NLI = lambda : list(NMI())
SI = lambda : input()

def make_grid(h, w, num):
	return [[int(num)] * w for _ in range(h)]

def main():
	(H, W, D) = NMI()
	grid = [NLI() for i in range(H)]
	Q = NI()
	querys = [NLI() for i in range(Q)]
	point = [[-1, -1] for _ in range(H * W + 1)]
	for h in range(H):
		for w in range(W):
			a = grid[h][w]
			point[a] = [h, w]
	cost_S = [0] * (H * W + 1)
	for c in range(H * W + 1):
		if c <= D:
			continue
		cost_S[c] = cost_S[c - D] + abs(point[c][0] - point[c - D][0]) + abs(point[c][1] - point[c - D][1])
	for query in querys:
		(l, r) = query
		print(cost_S[r] - cost_S[l])

def __starting_point():
	main()
__starting_point()


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
d = [0] * (H * W + 1)
g = [0] * (H * W + 1)
for i in range(H):
	for j in range(W):
		d[A[i][j]] = [i, j]
for i in range(1, H * W - D + 1):
	g[i + D] = abs(d[i + D][0] - d[i][0]) + abs(d[i + D][1] - d[i][1]) + g[i]
for q in range(Q):
	(l, r) = map(int, input().split())
	print(g[r] - g[l])


(h, w, d) = [int(x) for x in input().split()]
n = h * w
p_list = [None] * (n + 1)
for i in range(h):
	a_list = [int(x) for x in input().split()]
	for j in range(w):
		p_list[a_list[j]] = (i, j)
m_a_list = [0] * (n + 1)
for start in range(1, d + 1):
	(p_i, p_j) = p_list[start]
	p_target = start
	for target in range(start + d, n + 1, d):
		(n_i, n_j) = p_list[target]
		m = abs(n_i - p_i) + abs(n_j - p_j)
		m_a_list[target] = m + m_a_list[p_target]
		(p_i, p_j, p_target) = (n_i, n_j, target)
q = int(input())
for _ in range(q):
	(l, r) = [int(x) for x in input().split()]
	print(m_a_list[r] - m_a_list[l])


(h, w, d) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
x = [0] * (h * w + 1)
y = [0] * (h * w + 1)
ans = [0] * (h * w + 1)
for i in range(h):
	for j in range(w):
		x[a[i][j]] = i
		y[a[i][j]] = j
for i in range(d + 1, h * w + 1):
	ans[i] = ans[i - d] + abs(x[i] - x[i - d]) + abs(y[i] - y[i - d])
q = int(input())
for i in range(q):
	(l, r) = map(int, input().split())
	print(ans[r] - ans[l])


(h, w, d) = map(int, input().split())
a = []
for _ in range(h):
	a.append(list(map(int, input().split())))
q = int(input())
querys = []
for _ in range(q):
	(l, r) = map(int, input().split())
	querys.append((l - 1, r - 1))
coor = [None] * (h * w)
for i in range(h):
	for j in range(w):
		coor[a[i][j] - 1] = (i, j)
accu = [0] * (h * w)
for i in range(d, h * w):
	(px, py) = coor[i - d]
	(x, y) = coor[i]
	accu[i] = accu[i - d] + abs(x - px) + abs(y - py)
for (l, r) in querys:
	print(accu[r] - accu[l])


import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy
(H, W, D) = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(H)]
l = []
for h in range(H):
	for w in range(W):
		l.append((A[h][w], w, h))
l.sort()
S = [0] * (H * W + D + 10)
for (i, x, y) in l:
	if i + D <= H * W:
		(_, xx, yy) = l[i + D - 1]
		S[i + D] = abs(xx - x) + abs(yy - y) + S[i]
Q = int(input())
for i in range(Q):
	(L, R) = list(map(int, input().split()))
	print(S[R] - S[L])


import sys
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
import math
import bisect
INF = 1 << 50
EPS = 1e-08
mod = 998244353

def intread():
	return int(sysread())

def mapline(t=int):
	return list(map(t, sysread().split()))

def mapread(t=int):
	return list(map(t, read().split()))

def run():
	(H, W, D) = mapline()
	A = [[-1] * (W + 1) for _ in range(H + 1)]
	for i in range(1, H + 1):
		A[i][1:] = mapline()
	V = [-1] * (H * W + 1)
	for i in range(1, H + 1):
		for j in range(1, W + 1):
			V[A[i][j]] = (i, j)
	cache = [-1] * (H * W + 1)
	Q = intread()
	for _ in range(Q):
		(l, r) = mapline()
		if cache[r] == -1:
			mostR = r + (H * W - r) // D * D
			mostL = l % D
			if not mostL:
				mostL = D
			(ci, cj) = V[mostR]
			tmp = 0
			cache[mostR] = 0
			for v in range(mostR - D, mostL - D, -D):
				(ni, nj) = V[v]
				tmp += abs(ni - ci) + abs(nj - cj)
				cache[v] = tmp
				(ci, cj) = (ni, nj)
		print(cache[l] - cache[r])

def __starting_point():
	run()
__starting_point()


import sys
input = sys.stdin.readline
(H, W, D) = map(int, input().split())
cost = [[0 for _ in range(H * W // D + 1)] for i in range(D)]
L = [0] * (H * W)
for i in range(H):
	L1 = list(map(int, input().split()))
	for j in range(W):
		L[L1[j] - 1] = [i, j]
		if L1[j] % D != 0:
			cost[L1[j] % D][L1[j] // D] = [i, j, 0]
		else:
			cost[L1[j] % D][L1[j] // D - 1] = [i, j, 0]
for i in range(D):
	for j in range(1, len(cost[i])):
		if cost[i][j] != 0:
			cost[i][j][2] = cost[i][j - 1][2] + abs(cost[i][j][0] - cost[i][j - 1][0]) + abs(cost[i][j][1] - cost[i][j - 1][1])
Q = int(input())
for i in range(Q):
	(A, B) = map(int, input().split())
	c = A % D
	a = A // D
	b = B // D
	if c == 0:
		(a, b) = (a - 1, b - 1)
	print(cost[c][b][2] - cost[c][a][2])


(H, W, D) = map(int, input().split())
A = [None] * (H * W + 1)
for i in range(H):
	a = [int(i) for i in input().split()]
	for (j, v) in enumerate(a):
		A[v] = (i + 1, j + 1)
Q = int(input())
LR = [[int(i) for i in input().split()] for _ in range(Q)]
c = [0] * (H * W + 1)
for i in range(1 + D, W * H + 1):
	c[i] = c[i - D] + abs(A[i][0] - A[i - D][0]) + abs(A[i][1] - A[i - D][1])
for (l, r) in LR:
	print(c[r] - c[l])


(H, W, D) = map(int, input().split())
A = {}
for i in range(H):
	for (j, s) in enumerate(input().split()):
		A[int(s)] = [i, j]
Q = int(input())
exam = []
for i in range(Q):
	exam.append(list(map(int, input().split())))
grid = [0]
manta = lambda x, y: abs(x[0] - y[0]) + abs(x[1] - y[1])
for i in range(1, H * W + 1):
	if (i - 1) // D == 0:
		grid.append(0)
	else:
		grid.append(manta(A[i], A[i - D]) + grid[i - D])
for (l, r) in exam:
	print(grid[r] - grid[l])


(h, w, d) = map(int, input().split())
p = [(0, 0)] * (h * w)
c = [0] * (h * w)
for i in range(h):
	a = list(map(int, input().split()))
	for j in range(w):
		p[a[j] - 1] = (i, j)
for i in range(d, h * w):
	c[i] = c[i - d] + abs(p[i][0] - p[i - d][0]) + abs(p[i][1] - p[i - d][1])
q = int(input())
ans = 0
for i in range(q):
	(l, r) = map(int, input().split())
	print(c[r - 1] - c[l - 1])


F = lambda : map(int, input().split())
(H, W, D) = F()
d = {}
e = [0] * H * W
for i in range(H):
	for (j, v) in enumerate(F()):
		d[v - 1] = (i, j)
for i in range(H * W):
	if i >= D:
		e[i] = sum((abs(p - q) for (p, q) in zip(d[i - D], d[i]))) + e[i - D]
for i in range(int(input())):
	(l, r) = F()
	print(e[r - 1] - e[l - 1])


def main():
	from itertools import accumulate
	(h, w, d) = list(map(int, input().split()))
	a = [0] * (h * w + 1)
	b = [0] * (h * w + 1)
	for i in range(1, h + 1):
		l = list(map(int, input().split()))
		for (j, k) in enumerate(l, 1):
			a[k] = i
			b[k] = j
	c = [0] * (h * w + 1)
	for i in range(d + 1, h * w + 1):
		c[i] = c[i - d] + abs(a[i] - a[i - d]) + abs(b[i] - b[i - d])
	q = int(input())
	res = []
	for _ in range(q):
		(l, r) = list(map(int, input().split()))
		res.append(c[r] - c[l])
	ans = '\n'.join(map(str, res))
	print(ans)

def __starting_point():
	main()
__starting_point()


(h, w, d, *l) = map(int, open(0).read().split())
s = h * w
x = [0] * (s + 1)
y = [0] * (s + 1)
for (i, a) in enumerate(l[:s]):
	x[a] = i // w
	y[a] = i % w
ref = [0] * (s + 1)
for i in range(d + 1, s + 1):
	ref[i] = ref[i - d] + abs(x[i] - x[i - d]) + abs(y[i] - y[i - d])
for (l, r) in zip(l[s + 1::2], l[s + 2::2]):
	print(ref[r] - ref[l])


(h, w, d) = map(int, input().split())
from collections import defaultdict
G = defaultdict(list)
for i in range(h):
	l = list(map(int, input().split()))
	for (n, item) in enumerate(l):
		G[item] = [n, i]
dp = [0 for i in range(h * w + 1)]
for i in range(d):
	current_place = i + 1
	while current_place + d <= h * w:
		(x, y) = G[current_place]
		next_place = current_place + d
		(x1, y1) = G[next_place]
		magic = abs(x - x1) + abs(y - y1)
		dp[next_place] = magic + dp[current_place]
		current_place = next_place
q = int(input())
for i in range(q):
	(l, r) = map(int, input().split())
	print(dp[r] - dp[l], flush=True)


(h, w, d) = map(int, input().split())
box = [list(map(int, input().split())) for i in range(h)]
adress = {}
for i in range(h):
	for j in range(w):
		adress[box[i][j]] = [i, j]
q = int(input())
order = [list(map(int, input().split())) for i in range(q)]
S = [0] * (h * w + 1)
for k in range(d + 1, h * w + 1):
	(x, y) = adress[k]
	(i, j) = adress[k - d]
	S[k] = S[k - d] + abs(x - i) + abs(y - j)
for (x, y) in order:
	print(S[y] - S[x])


import sys
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 9)
(h, w, d) = list(map(int, input().split()))
inds = {}
for i in range(h):
	for (D, j) in enumerate(input().split()):
		inds[int(j) - 1] = (i, D)
nows = [[0] for c in range(d)]
for k in range(d, h * w):
	(a, b) = inds[k]
	(x, y) = inds[k - d]
	k %= d
	nows[k].append(nows[k][-1] + abs(a - x) + abs(b - y))
q = input()
for i in inputs():
	(l, r) = list(map(int, i.split()))
	l -= 1
	r -= 1
	(l, b) = divmod(l, d)
	(r, b) = divmod(r, d)
	print(nows[b][r] - nows[b][l])


(h, w, d) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]
x = [[] for _ in range(h * w)]
for i in range(h):
	for j in range(w):
		x[a[i][j] - 1] = [i, j]
z = [0 for _ in range(h * w)]
for i in range(d):
	for j in range(i + d, h * w, d):
		z[j] = z[j - d] + abs(x[j][0] - x[j - d][0]) + abs(x[j][1] - x[j - d][1])
for t in lr:
	print(z[t[1] - 1] - z[t[0] - 1])


(h, w, d) = map(int, input().split())
arr = [0] * (h * w + 1)
a = [list(map(int, input().split())) for _ in range(h)]
for i in range(h):
	for j in range(w):
		s = a[i][j]
		arr[s] = (i, j)
q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]
cnt = h * w
result = [[0] for _ in range(d)]
for i in range(d):
	l = i
	score = 0
	while l + d <= cnt:
		if l == 0:
			result[i].append(score)
			l += d
			continue
		(ux, uy) = arr[l]
		(vx, vy) = arr[l + d]
		score += abs(vx - ux) + abs(vy - uy)
		result[i].append(score)
		l += d
for (l, r) in lr:
	ans = result[l % d]
	print(ans[r // d] - ans[l // d])


(H, W, D) = map(int, input().split())
number = [[0, 0] for _ in range(H * W)]
cost = [0] * (H * W)
for i in range(H):
	a = list(map(int, input().split()))
	for j in range(W):
		number[a[j] - 1] = [i, j]
for i in range(D):
	cost[i] = 0
for j in range(D, H * W):
	cost[j] = cost[j - D] + abs(number[j][0] - number[j - D][0]) + abs(number[j][1] - number[j - D][1])
Q = int(input())
for i in range(Q):
	(L, R) = map(int, input().split())
	print(cost[R - 1] - cost[L - 1])


(h, w, d) = map(int, input().split(' '))
comp = {}
for i in range(h):
	tmp = list(map(int, input().split(' ')))
	for j in range(w):
		comp[tmp[j]] = [i, j]
q = int(input())
lr = [map(int, input().split(' ')) for _ in range(q)]
dp = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
	cnt = dp[i - d]
	cnt += abs(comp[i][0] - comp[i - d][0])
	cnt += abs(comp[i][1] - comp[i - d][1])
	dp[i] = cnt
for (l, r) in lr:
	print(dp[r] - dp[l])


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
P = [(0, 0)] * (H * W + 1)
for i in range(H):
	for j in range(W):
		P[A[i][j]] = (i, j)
d = [0] * (H * W + 1)
for i in range(D + 1, H * W + 1):
	d[i] = d[i - D] + abs(P[i][0] - P[i - D][0]) + abs(P[i][1] - P[i - D][1])
Q = int(input())
for _ in range(Q):
	(L, R) = map(int, input().split())
	print(d[R] - d[L])


(H, W, D) = [int(i) for i in input().split()]
px = [0] * 90001
py = [0] * 90001
for i in range(H):
	a = [int(i) for i in input().split()]
	for (j, v) in enumerate(a):
		px[v] = j
		py[v] = i
d = [0] * 90001
for i in range(D + 1, 90001):
	d[i] = d[i - D] + abs(px[i] - px[i - D]) + abs(py[i] - py[i - D])
Q = int(input())
for i in range(Q):
	(L, R) = map(int, input().split())
	ans = d[R] - d[L]
	print(ans)


(h, w, d) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
dic = {}
q = int(input())
for i in range(h):
	for j in range(w):
		dic[a[i][j]] = (i, j)
li = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
	if i - d not in dic:
		continue
	li[i] = li[i - d] + abs(dic[i][0] - dic[i - d][0]) + abs(dic[i][1] - dic[i - d][1])
for _ in range(q):
	(l, r) = map(int, input().split())
	print(li[r] - li[l])


import sys, math, collections, itertools
input = sys.stdin.readline
(H, W, D) = list(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)]
dict_map = {}
for ih in range(H):
	for iw in range(W):
		dict_map[A[ih][iw]] = (ih, iw)
memo = [-1] * (H * W + 1)
for i in range(1, D + 1):
	useMP = 0
	direct = list(range(i, H * W + 1, D))
	memo[i] = 0
	for p in range(len(direct) - 1):
		(x0, y0) = dict_map[direct[p]]
		(x1, y1) = dict_map[direct[p + 1]]
		dist = abs(x0 - x1) + abs(y0 - y1)
		useMP += dist
		memo[direct[p + 1]] = useMP
for q in range(Q):
	(L, R) = LR[q]
	print(memo[R] - memo[L])


(h, w, d) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
LR = [list(map(int, input().split())) for _ in range(q)]
B = [[] for _ in range(h * w + 1)]
for i in range(h):
	for j in range(w):
		B[A[i][j]] = [i, j]
DP = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
	(x, y) = B[i]
	(z, w) = B[i - d]
	DP[i] = DP[i - d] + abs(x - z) + abs(y - w)
for (l, r) in LR:
	print(DP[r] - DP[l])


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
x = [0] * (H * W + 1)
p = [[] for _ in range(H * W + 1)]
for h in range(H):
	for w in range(W):
		p[A[h][w]] = [h, w]
for i in range(D + 1, H * W + 1):
	x[i] = x[i - D] + abs(p[i][0] - p[i - D][0]) + abs(p[i][1] - p[i - D][1])
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(x[r] - x[l])


(H, W, D) = map(int, input().split())
d = [[0, 0] for i in range(H * W + 1)]
d2 = [0 for i in range(H * W + 1)]
for j in range(H):
	a = [int(x) for x in input().split()]
	for k in range(W):
		d[a[k]] = [j + 1, k + 1]
for l in range(D + 1, H * W + 1):
	d2[l] = abs(d[l][0] - d[l - D][0]) + abs(d[l][1] - d[l - D][1])
for m in range(D + 1, H * W + 1):
	d2[m] += d2[m - D]
Q = int(input())
for i in range(Q):
	(a, b) = map(int, input().split())
	if a == b:
		print(0)
	else:
		ans = d2[b] - d2[a]
		print(ans)


(h, w, d) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
r = [None for i in range(h * w + 1)]
for i in range(h):
	for j in range(w):
		r[a[i][j]] = (i, j)
c = [0 for i in range(h * w + 1)]
for i in range(d + 1, h * w + 1):
	c[i] = c[i - d] + abs(r[i][0] - r[i - d][0]) + abs(r[i][1] - r[i - d][1])
q = int(input())
for _ in range(q):
	(x, y) = map(int, input().split())
	print(c[y] - c[x])


(H, W, D) = map(int, input().split())
X = [0] * (H * W + 1)
for i in range(H):
	j = 0
	for a in input().split():
		X[int(a)] = (i, j)
		j += 1
S = [0] * (H * W + 1)
for i in range(1, H * W + 1):
	if i + D <= H * W:
		S[i + D] += S[i] + abs(X[i + D][0] - X[i][0]) + abs(X[i + D][1] - X[i][1])
Q = int(input())
for q in range(Q):
	(l, r) = map(int, input().split())
	print(S[r] - S[l])


(H, W, D) = list(map(int, input().split()))
base = []
for h in range(H):
	num = list(map(int, input().split()))
	for w in range(W):
		base.append((num[w], h + 1, w + 1))
base.sort(key=lambda tup: tup[0])
dist = [0] * (W * H + D + 1)
for i in range(W * H - D):
	(wei1, h1, w1) = base[i]
	(wei2, h2, w2) = base[i + D]
	dist[i + D] = dist[i] + abs(h1 - h2) + abs(w1 - w2)
Q = int(input())
for _ in range(Q):
	(p0, p1) = list(map(int, input().split()))
	print(abs(dist[p1 - 1] - dist[p0 - 1]))


(H, W, D) = map(int, input().split())
px = [0] * (H * W + 1)
py = [0] * (H * W + 1)
dp = [0] * (H * W + 1)
for i in range(H):
	inf = input().split()
	for j in range(W):
		a = int(inf[j])
		py[a] = i
		px[a] = j
for i in range(D + 1, H * W + 1):
	dp[i] = dp[i - D] + abs(px[i] - px[i - D]) + abs(py[i] - py[i - D])
Q = int(input())
for i in range(Q):
	(L, R) = map(int, input().split())
	print(dp[R] - dp[L])


(h, w, d) = map(int, input().split())
whereA = [[0, 0] for _ in range(h * w)]
for i in range(h):
	A = list(map(int, input().split()))
	for (j, a) in enumerate(A):
		whereA[a - 1] = [i, j]
Dsum = [0] * (h * w)
for i in range(h * w):
	Dsum[i] = Dsum[max(i - d, i % d)] + abs(whereA[i][0] - whereA[max(i - d, i % d)][0]) + abs(whereA[i][1] - whereA[max(i - d, i % d)][1])
q = int(input())
for _ in range(q):
	(l, r) = map(int, input().split())
	print(Dsum[r - 1] - Dsum[l - 1])


def i1():
	return int(input())

def i2():
	return [int(i) for i in input().split()]
[h, w, d] = i2()
a = []
for i in range(h):
	s = i2()
	for j in range(w):
		a.append([s[j], [i, j]])
q = i1()
lr = []
for i in range(q):
	lr.append(i2())
a = sorted(a)
f = [0 for i in range(h * w)]
for i in range(h * w - d):
	f[i + d] = f[i] + abs(a[i][1][0] - a[i + d][1][0]) + abs(a[i][1][1] - a[i + d][1][1])
for i in lr:
	print(f[i[1] - 1] - f[i[0] - 1])


(H, W, D) = list(map(int, input().split()))
(d, px, py) = ([0] * (H * W + 1), [0] * (H * W + 1), [0] * (H * W + 1))
for i in range(H):
	a = list(map(int, input().split()))
	for j in range(W):
		px[a[j]] = i
		py[a[j]] = j
for i in range(D + 1, H * W + 1):
	d[i] = d[i - D] + abs(px[i] - px[i - D]) + abs(py[i] - py[i - D])
Q = int(input())
for _ in range(Q):
	(l, r) = list(map(int, input().split()))
	print(d[r] - d[l])


(H, W, D) = map(int, input().split())
px = [0 for k in range(H * W + D + 1)]
py = [0 for k in range(H * W + D + 1)]
S = [list(map(int, input().split())) for k in range(H)]
for j in range(W):
	for i in range(H):
		px[S[i][j]] = i
		py[S[i][j]] = j
d = [0 for k in range(H * W + D + 1)]
for k in range(H * W, 0, -1):
	d[k] = d[k + D] + abs(px[k] - px[k + D]) + abs(py[k] - py[k + D])
Q = int(input())
for k in range(Q):
	(L, R) = map(int, input().split())
	print(d[L] - d[R])


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])


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [tuple(map(int, input().split())) for _ in range(Q)]
pos = [None] * (H * W)
for i in range(H):
	for j in range(W):
		pos[A[i][j] - 1] = (i, j)
d = [0] * (H * W)
for i in range(D, H * W):
	(px, py) = pos[i - D]
	(x, y) = pos[i]
	d[i] = d[i - D] + abs(x - px) + abs(y - py)
for (l, r) in LR:
	print(d[r - 1] - d[l - 1])


from itertools import accumulate

def get_dist(cur, nxt):
	return abs(cur[0] - nxt[0]) + abs(cur[1] - nxt[1])
(H, W, D) = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(H)]
pos = {}
for i in range(H):
	for j in range(W):
		pos[A[i][j] - 1] = (i, j)
acc = []
for i in range(D):
	res = [0]
	now = i
	while now + D < H * W:
		nxt = now + D
		res.append(get_dist(pos[now], pos[nxt]))
		now = nxt
	acc.append(list(accumulate(res)))
Q = int(input())
for _ in range(Q):
	ans = 0
	(L, R) = list(map(int, input().split()))
	L -= 1
	R -= 1
	path = acc[L % D]
	print(path[R // D] - path[L // D])


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
x = [0] * (H * W + D + 1)
y = [0] * (H * W + D + 1)
for k in range(W):
	for l in range(H):
		x[A[l][k]] = k + 1
		y[A[l][k]] = l + 1
d = [0] * (H * W + D + 1)
for k in range(H * W, 0, -1):
	d[k] = d[k + D] + abs(x[k] - x[k + D]) + abs(y[k] - y[k + D])
for _ in range(int(input())):
	(L, R) = map(int, input().split())
	print(d[L] - d[R])


(h, w, d) = map(int, input().split())
dic = {}
for i in range(h):
	line = list(map(int, input().split()))
	for j in range(w):
		dic[line[j] - 1] = (i, j)
A = [0] * (h * w)
for i in range(h * w - d):
	(x, y) = dic[i]
	(nx, ny) = dic[i + d]
	A[i + d] = A[i] + abs(nx - x) + abs(ny - y)
q = int(input())
for i in range(q):
	(l, r) = map(int, input().split())
	print(A[r - 1] - A[l - 1])


(H, W, D) = list(map(int, input().split()))
A = []
for h in range(H):
	A.append(list(map(int, input().split())))
pos = {}
for h in range(H):
	for w in range(W):
		pos[A[h][w]] = [h, w]
S = [0] * (H * W)
for d in range(D):
	tmp = 0
	now = d + 1
	while now + D <= H * W:
		(nowh, noww) = pos[now]
		(newh, neww) = pos[now + D]
		tmp += abs(nowh - newh) + abs(noww - neww)
		S[now + D - 1] = tmp
		now += D
Q = int(input())
for i in range(Q):
	(L, R) = list(map(int, input().split()))
	ans = S[R - 1] - S[L - 1]
	print(ans)


(h, w, d) = map(int, input().split())
num = [0] * (h * w)
for i in range(h):
	a = list(map(int, input().split()))
	for j in range(w):
		num[a[j] - 1] = (i, j)
cost = [0] * (h * w)
for i in range(d, h * w):
	cost[i] = cost[i - d] + abs(num[i][0] - num[i - d][0]) + abs(num[i][1] - num[i - d][1])
q = int(input())
ans = [0] * q
for i in range(q):
	(l, r) = map(int, input().split())
	ans[i] = cost[r - 1] - cost[l - 1]
print(*ans, sep='\n')


(H, W, D) = map(int, input().split())
A_where = [0] * (H * W + 1)
A_where[0] = (-1, -1)
for p in range(H):
	A = list(map(int, input().split()))
	for q in range(W):
		A_where[A[q]] = (p, q)
Q = int(input())
DP = [0] * (H * W + 1)
for i in range(D + 1, H * W + 1):
	(y1, x1) = A_where[i]
	(y2, x2) = A_where[i - D]
	DP[i] = DP[i - D] + abs(y1 - y2) + abs(x1 - x2)
for i in range(Q):
	(l, r) = map(int, input().split())
	print(DP[r] - DP[l])


(h, w, d) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(h)]
n = h * w
L = [0] * (n + 1)

def dis(p, q):
	return abs(p[0] - q[0]) + abs(p[1] - q[1])
for i in range(h):
	for j in range(w):
		t = A[i][j]
		L[t] = (i, j)
K = [0] * (n + 1)
for i in range(1, n - d + 1):
	K[i + d] = dis(L[i + d], L[i])
	K[i + d] += K[i]
q = int(input())
for _ in range(q):
	(l, r) = map(int, input().split())
	print(K[r] - K[l])


(H, W, D) = list(map(int, input().split()))
map_ = [[0, 0] for _ in range(H * W + 1)]
for y in range(H):
	for (x, A) in enumerate(map(int, input().split())):
		map_[A] = [x + 1, y + 1]
cost = [0 for _ in range(H * W + 1)]
for i in range(D + 1, H * W + 1):
	cost[i] += abs(map_[i][0] - map_[i - D][0]) + abs(map_[i][1] - map_[i - D][1]) + cost[i - D]
Q = int(input())
for i in range(Q):
	(L, R) = list(map(int, input().split()))
	print(cost[R] - cost[L])


(H, W, D) = map(int, input().split())
A = [-1] * (H * W + 1)
cnt = 0
for i in range(H):
	for j in list(map(int, input().split())):
		A[j] = cnt
		cnt += 1
dp = [0] * (H * W + 1)
tmp = 1
for i in range(D):
	(h, w) = (A[tmp] // W + 1, A[tmp] % W + 1)
	t = tmp + D
	cnt = 0
	while t <= H * W:
		(x, y) = (A[t] // W + 1, A[t] % W + 1)
		cnt += abs(x - h) + abs(y - w)
		dp[t] = cnt
		(h, w) = (x, y)
		t += D
	tmp += 1
Q = int(input())
for i in range(Q):
	(l, r) = map(int, input().split())
	ans = dp[r] - dp[l]
	print(ans)


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
P = [None] * (H * W + 1)
for i in range(H):
	for j in range(W):
		P[A[i][j]] = (i, j)
C = [0] * (H * W + 1)
for i in range(D + 1, H * W + 1):
	(pi, pj) = P[i]
	(qi, qj) = P[i - D]
	C[i] = C[i - D] + abs(pi - qi) + abs(pj - qj)
ans = []
Q = int(input())
for _ in range(Q):
	(L, R) = map(int, input().split())
	ans.append(C[R] - C[L])
print(*ans, sep='\n')


(h, w, d) = map(int, input().split())
hw = [[] for _ in range(h * w + 1)]
for i in range(h):
	row = list(map(int, input().split()))
	for j in range(w):
		hw[row[j]] = [i, j]
a = [0 for _ in range(h * w + 1)]
for i in range(d + 1, h * w + 1):
	a[i] = a[i - d] + abs(hw[i][0] - hw[i - d][0]) + abs(hw[i][1] - hw[i - d][1])
q = int(input())
for i in range(q):
	(L, R) = map(int, input().split())
	print(a[R] - a[L])


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
lr = [list(map(int, input().split())) for _ in range(Q)]
C = {}
for i in range(H):
	for j in range(W):
		C[A[i][j]] = [j, i]
S = [0] * (H * W + 1)
i = D + 1
while i < H * W + 1:
	(x1, y1) = (C[i][0], C[i][1])
	(x2, y2) = (C[i - D][0], C[i - D][1])
	S[i] = S[i - D] + abs(x2 - x1) + abs(y2 - y1)
	i += 1
for (l, r) in lr:
	q = S[r] - S[l]
	print(q)


(h, w, d) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]
nums = {}
for i in range(h):
	for j in range(w):
		nums[a[i][j]] = (i, j)
acc = [0] * (h * w)
for i in range(h * w):
	if i >= d:
		_to = nums[i + 1]
		_from = nums[i + 1 - d]
		acc[i] += acc[i - d] + abs(_from[0] - _to[0]) + abs(_from[1] - _to[1])
for (l, r) in lr:
	print(acc[r - 1] - acc[l - 1])


(H, W, D) = map(int, input().split())
x_axis = [0] * (H * W)
y_axis = [0] * (H * W)
for i in range(H):
	A = list(map(lambda x: int(x) - 1, input().split()))
	for j in range(W):
		x_axis[A[j]] = j
		y_axis[A[j]] = i

def dis(a, b):
	return abs(x_axis[a] - x_axis[b]) + abs(y_axis[a] - y_axis[b])
magic = [[0] for _ in range(D)]
for i in range(D):
	temp = i
	while temp < H * W - D:
		magic[i].append(magic[i][-1] + dis(temp, temp + D))
		temp += D
Q = int(input())
for _ in range(Q):
	(L, R) = map(lambda x: int(x) - 1, input().split())
	(L, d) = divmod(L, D)
	R //= D
	print(magic[d][R] - magic[d][L])


(h, w, d) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
l = [list(map(int, input().split())) for _ in range(q)]
dic = {}
for i in range(len(a)):
	for j in range(len(a[i])):
		dic[a[i][j]] = (i, j)
sum = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
	sum[i] = sum[i - d] + abs(dic[i][0] - dic[i - d][0]) + abs(dic[i][1] - dic[i - d][1])
for l_ in l:
	print(sum[l_[1]] - sum[l_[0]])


(H, W, D) = map(int, input().split())
A = []
for j in range(H):
	for (i, a) in enumerate(map(int, input().split())):
		A.append([a, i, j])
A.sort()
lenA = len(A)
points = [0] * lenA
for inia in [i for i in range(D)]:
	i = inia + D
	while i < lenA:
		points[i] = points[i - D] + abs(A[i][1] - A[i - D][1]) + abs(A[i][2] - A[i - D][2])
		i += D
Q = int(input())
for _ in range(Q):
	(l, r) = map(int, input().split())
	print(points[r - 1] - points[l - 1])


import sys
readline = sys.stdin.readline
(h, w, d) = map(int, readline().split())
A = [list(map(int, readline().split())) for _ in range(h)]
q = int(readline())
LR = [tuple(map(lambda x: int(x) - 1, readline().split())) for _ in range(q)]
D = dict()
for hi in range(h):
	for wi in range(w):
		D[A[hi][wi] - 1] = [hi, wi]
DP = [0] * (h * w)
for i in range(d, h * w):
	(px, py) = D[i - d]
	(x, y) = D[i]
	DP[i] = DP[i - d] + abs(x - px) + abs(y - py)
for (l, r) in LR:
	print(DP[r] - DP[l])


import sys
input = sys.stdin.readline
(h, w, d) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
x = [0] * (h * w + 1)
y = [0] * (h * w + 1)
for i in range(1, h + 1):
	for j in range(1, w + 1):
		x[a[i - 1][j - 1]] = i
		y[a[i - 1][j - 1]] = j
dp = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
	dp[i] = dp[i - d] + abs(x[i] - x[i - d]) + abs(y[i] - y[i - d])
q = int(input())
for _ in range(q):
	(l, r) = map(int, input().split())
	print(dp[r] - dp[l])


(h, w, d) = map(int, input().split())
A = [[0] * w for i in range(h)]
B = [0] * (w * h)
C = [0] * (w * h)
for i in range(h):
	A[i] = list(map(int, input().split()))
	for j in range(w):
		B[A[i][j] - 1] = i
		C[A[i][j] - 1] = j
D = [0] * (h * w)
for i in range(d, w * h):
	D[i] = D[i - d] + abs(B[i - d] - B[i]) + abs(C[i - d] - C[i])
q = int(input())
for i in range(q):
	(a, b) = map(int, input().split())
	print(D[b - 1] - D[a - 1])


(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)]
pos = [(-1, -1) for i in range(H * W + 1)]
for h in range(H):
	for w in range(W):
		pos[A[h][w]] = (h, w)
cost = [0] * (H * W + 1)
for i in range(1 + D, H * W + 1):
	cost[i] = cost[i - D] + abs(pos[i][0] - pos[i - D][0]) + abs(pos[i][1] - pos[i - D][1])
for q in range(Q):
	print(cost[LR[q][1]] - cost[LR[q][0]])


(h, w, d) = map(int, input().split())
ind = {}
for i in range(h):
	l = list(map(int, input().split()))
	for j in range(w):
		ind[l[j]] = (i, j)
dp = [0] * (h * w)
for i in range(d + 1, h * w + 1):
	(x, y) = ind[i]
	(z, q) = ind[i - d]
	dp[i - 1] = abs(z - x) + abs(y - q) + dp[i - d - 1]
q = int(input())
for i in range(q):
	(l, r) = map(int, input().split())
	print(dp[r - 1] - dp[l - 1])


(h, w, d) = map(int, input().split())
dic = {}
for i in range(h):
	a = input().split()
	for j in range(w):
		dic[int(a[j])] = (i + 1, j + 1)
q = int(input())
c = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
	(pi, pj) = dic[i]
	(qi, qj) = dic[i - d]
	c[i] = c[i - d] + abs(pi - qi) + abs(pj - qj)
for i in range(q):
	(l, r) = map(int, input().split())
	print(c[r] - c[l])


(H, W, D) = [int(x) for x in input().split()]
size = H * W + 1
c = [(-1, -1)] * size
p = [0] * size
for y in range(H):
	for (x, a) in enumerate([int(s) for s in input().split()]):
		c[a] = (x, y)
for a in range(D + 1, size):
	p[a] = p[a - D] + abs(c[a][0] - c[a - D][0]) + abs(c[a][1] - c[a - D][1])
Q = int(input())
for i in range(Q):
	(L, R) = [int(lr) for lr in input().split()]
	print(p[R] - p[L])


(H, W, D) = map(int, input().split())
S = H * W
A = [map(int, input().split()) for _ in range(H)]
d = [0] * S
e = [0] * S
for (i, l) in enumerate(A):
	for (j, v) in enumerate(l):
		d[v - 1] = (i, j)
for i in range(S):
	if i >= D:
		e[i] = sum((abs(p - q) for (p, q) in zip(d[i - D], d[i]))) + e[i - D]
for i in range(int(input())):
	(l, r) = map(int, input().split())
	print(e[r - 1] - e[l - 1])


import sys
import numba as nb
import numpy as np
input = sys.stdin.readline

@nb.njit('void(i8,i8,i8,i8[:,:],i8,i8[:,:],i8[:])', cache=True)
def dfs(H, W, D, A, Q, LR, ans):
	position = [(-1, -1)] * (H * W + 1)
	for h in range(H):
		for w in range(W):
			position[A[h][w]] = (h, w)
	mp = np.zeros(shape=H * W + 1, dtype=np.int64)
	for i in range(1, H * W + 1 - D):
		(h, w) = position[i]
		(y, x) = position[i + D]
		mp[i + D] = abs(x - w) + abs(y - h)
	for d in range(1, D + 1):
		mp[d::D] = np.cumsum(mp[d::D])
	for i in range(Q):
		(l, r) = LR[i]
		ans[i] = mp[r] - mp[l]

def main():
	(H, W, D) = list(map(int, input().split()))
	A = np.zeros(shape=(H, W), dtype=np.int64)
	for i in range(H):
		A[i] = tuple(map(int, input().split()))
	Q = int(input())
	LR = np.zeros(shape=(Q, 2), dtype=np.int64)
	for i in range(Q):
		LR[i] = tuple(map(int, input().split()))
	ans = np.zeros(shape=Q, dtype=np.int64)
	dfs(H, W, D, A, Q, LR, ans)
	print('\n'.join(map(str, ans)))

def __starting_point():
	main()
__starting_point()


(h, w, d) = map(int, input().split())
l = [[0, 0]] + [[] for _ in range(h * w)]
for i in range(h):
	for (j, a) in enumerate(map(int, input().split())):
		l[a] = [i, j]
for i in range(h * w + 1):
	if i < d:
		l[i].append(0)
	else:
		(a, b) = l[i]
		(x, y, v) = l[i - d]
		l[i].append(abs(x - a) + abs(y - b) + v)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(l[b][2] - l[a][2])


(h, w, d) = map(int, input().split())
a = []
box = [[] for i in range(h * w + 1)]
wi = 0
for i in range(h):
	ai = list(map(int, input().split()))
	for j in range(w):
		box[ai[j]] = [i, j]
p = [0]
for i in range(1, h * w + 1):
	if i - d > 0:
		p.append(p[i - d] + abs(box[i][0] - box[i - d][0]) + abs(box[i][1] - box[i - d][1]))
	else:
		p.append(0)
q = int(input())
for i in range(q):
	(l, r) = map(int, input().split())
	print(p[r] - p[l])


def getlist():
	return list(map(int, input().split()))
(H, W, D) = getlist()
a = []
mp = [0] * (H * W + 1)
for i in range(H):
	A = getlist()
	for j in range(W):
		a.append([A[j], i, j])
a = sorted(a)
for i in range(D, H * W):
	mp[i] += mp[i - D] + abs(a[i][1] - a[i - D][1]) + abs(a[i][2] - a[i - D][2])
Q = int(input())
for i in range(Q):
	(L, R) = getlist()
	print(mp[R - 1] - mp[L - 1])


(h, w, d) = map(int, input().split())
dict = {}
for i in range(1, h + 1):
	lst = list(map(int, input().split()))
	for j in range(w):
		dict.setdefault(lst[j], (i, j + 1))
cost = [0] * (h * w)
for i in range(d, h * w):
	cost[i] = cost[i - d] + abs(dict[i - d + 1][0] - dict[i + 1][0]) + abs(dict[i - d + 1][1] - dict[i + 1][1])
ans = 0
q = int(input())
for i in range(q):
	ans = 0
	(l, r) = map(int, input().split())
	print(cost[r - 1] - cost[l - 1])


(h, w, d) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
e = [[] for _ in range(h * w + 1)]
dp = [0] * (h * w + 1)
for i in range(h):
	for j in range(w):
		e[a[i][j]] = (i, j)
for i in range(1, h * w + 1 - d):
	dp[i + d] = dp[i] + abs(e[i + d][0] - e[i][0]) + abs(e[i + d][1] - e[i][1])
q = int(input())
for _ in range(q):
	(l, r) = map(int, input().split())
	print(dp[r] - dp[l])


(h, w, d) = map(int, input().split())
a = {}
for y in range(h):
	tmp = list(map(int, input().split()))
	for (x, v) in enumerate(tmp):
		a[v] = (y, x)
dis = [0] * (h * w + 1)
for i in range(1, h * w + 1):
	if i > d:
		bk = a[i - d]
		nx = a[i]
		dis[i] = dis[i - d] + abs(bk[0] - nx[0]) + abs(bk[1] - nx[1])
q = int(input())
ans = []
for _ in range(q):
	(start, goal) = map(int, input().split())
	ans.append(dis[goal] - dis[start])
for item in ans:
	print(item)


def main():
	import sys
	sys.setrecursionlimit(1000000)
	(h, w, d) = list(map(int, input().split()))
	p = []
	for i in range(1, h + 1):
		l = list(map(int, input().split()))
		for (j, k) in enumerate(l, 1):
			p.append((k, (i, j)))
	p.sort(key=lambda x: x[0])
	q = int(input())
	dist = [0] * (w * h + 1)

	def Q(i, c, x, y):
		if i + d > w * h:
			return
		(_, (nx, ny)) = p[i + d - 1]
		nc = c + abs(nx - x) + abs(ny - y)
		dist[i + d] = nc
		Q(i + d, nc, nx, ny)
	for i in range(d):
		(n, (x, y)) = p[i]
		Q(n, 0, x, y)
	res = []
	for _ in range(q):
		(l, r) = list(map(int, input().split()))
		res.append(dist[r] - dist[l])
	ans = '\n'.join(map(str, res))
	print(ans)

def __starting_point():
	main()
__starting_point()


(h, w, d) = map(int, input().split())
dp = [0] * (h * w + 1)
ab = [list(map(int, input().split())) for _ in range(h)]
for i in range(h):
	for j in range(w):
		s = ab[i][j]
		dp[s] = [i, j]
dpp = [0] * (h * w + 1)
for k in range(d + 1, h * w + 1):
	dpp[k] = dpp[k - d] + abs(dp[k][0] - dp[k - d][0]) + abs(dp[k][1] - dp[k - d][1])
q = int(input())
for x in range(q):
	(a, b) = map(int, input().split())
	print(dpp[b] - dpp[a])


import itertools
I = [int(_) for _ in open(0).read().split()]
(H, W, D) = I[:3]
A = I[3:3 + H * W]
Q = I[3 + H * W]
LR = I[4 + H * W:]
a_i = [0] * (H * W + 1)
for (i, a) in enumerate(A):
	a_i[a] = i

def calc(a1):
	a2 = a1 + D
	hw1 = a_i[a1]
	(h1, w1) = divmod(hw1, W)
	hw2 = a_i[a2]
	(h2, w2) = divmod(hw2, W)
	return abs(h2 - h1) + abs(w2 - w1)
score = [0] + [calc(i) for i in range(1, H * W + 1 - D)]
cum = [[0] + list(itertools.accumulate(score[i::D])) for i in range(D)]
ans = []
for (l, r) in zip(LR[::2], LR[1::2]):
	ans += [cum[r % D][r // D] - cum[l % D][l // D]]
print(*ans, sep='\n')


(H, W, D) = map(int, input().split())
masu = []
for j in range(H):
	L = list(map(int, input().split()))
	for i in range(W):
		masu.append(tuple((L[i], j + 1, i + 1)))
masu = sorted(masu, key=lambda x: x[0])
dp = [0] * (H * W)
for i in range(D, H * W):
	dp[i] = dp[i - D] + abs(masu[i][1] - masu[i - D][1]) + abs(masu[i][2] - masu[i - D][2])
Q = int(input())
for _ in range(Q):
	(L, R) = map(int, input().split())
	print(dp[R - 1] - dp[L - 1])


def resolve():
	(H, W, D) = list(map(int, input().split()))
	A = [list(map(int, input().split())) for _ in range(H)]
	Q = int(input())
	LR = [list(map(int, input().split())) for _ in range(Q)]
	num_to_pos = {}
	for i in range(H):
		for j in range(W):
			num_to_pos[A[i][j]] = (i, j)
	acc = [[0] for _ in range(D + 1)]
	for i in range(1, D + 1):
		num = i
		idx = 0
		while num + D <= H * W:
			_from = num_to_pos[num]
			_to = num_to_pos[num + D]
			acc[i].append(acc[i][idx] + abs(_from[0] - _to[0]) + abs(_from[1] - _to[1]))
			num += D
			idx += 1
	for lr in LR:
		(l, r) = lr
		series = l % D if l % D != 0 else D
		print(acc[series][(r - series) // D] - acc[series][(l - series) // D])
if '__main__' == __name__:
	resolve()


def get_dist(cur, nxt):
	return abs(cur[0] - nxt[0]) + abs(cur[1] - nxt[1])
(H, W, D) = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(H)]
pos = {}
for i in range(H):
	for j in range(W):
		pos[A[i][j]] = (i, j)
acc = [0] * (H * W + 1)
for i in range(D + 1, H * W + 1):
	acc[i] = acc[i - D] + get_dist(pos[i - D], pos[i])
Q = int(input())
for _ in range(Q):
	ans = 0
	(L, R) = list(map(int, input().split()))
	print(acc[R] - acc[L])


def dist(x, y):
	return abs(x[0] - y[0]) + abs(x[1] - y[1])
(H, W, D) = map(int, input().split())
G = {}
for i in range(H):
	row = list(map(int, input().split()))
	for j in range(W):
		G[row[j]] = (i, j)
B = {i: 0 for i in range(1, D + 1)}
for i in range(1, D + 1):
	for j in range(i + D, H * W + 1, D):
		B[j] = B[j - D] + dist(G[j - D], G[j])
Q = int(input())
for _ in range(Q):
	(L, R) = map(int, input().split())
	print(B[R] - B[L])


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
in_n = lambda : int(readline())
in_nn = lambda : list(map(int, readline().split()))
in_nl = lambda : list(map(int, readline().split()))
in_na = lambda : list(map(int, read().split()))
in_s = lambda : readline().rstrip().decode('utf-8')

def main():
	(H, W, D) = in_nn()
	A = [list(map(int, readline().split())) for _ in range(H)]
	Q = in_n()
	LR = [list(map(int, readline().split())) for _ in range(Q)]
	grid = [tuple()] * (H * W + 1)
	for y in range(H):
		for x in range(W):
			num = A[y][x]
			grid[num] = (x + 1, y + 1)
	move = [[] for _ in range(D)]
	for i in range(D):
		if i == 0:
			s = D
		else:
			s = i
		while s <= H * W:
			move[i].append(grid[s])
			s += D
	d = [[] for _ in range(D)]
	for i in range(D):
		d[i].append(0)
		for j in range(len(move[i]) - 1):
			(x, y) = move[i][j]
			(nx, ny) = move[i][j + 1]
			d[i].append(abs(nx - x) + abs(ny - y))
	for i in range(D):
		for j in range(len(d[i]) - 1):
			d[i][j + 1] += d[i][j]
	ans = [0] * Q
	for i in range(Q):
		(l, r) = LR[i]
		(q1, rr) = divmod(l, D)
		(q2, _) = divmod(r, D)
		if rr == 0:
			ans[i] = d[rr][q2 - 1] - d[rr][q1 - 1]
		else:
			ans[i] = d[rr][q2] - d[rr][q1]
	print('\n'.join(map(str, ans)))

def __starting_point():
	main()
__starting_point()


(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])


def main():
	(h, w, d) = map(int, input().split())
	a = []
	for i in range(h):
		a.append(list(map(int, input().split())))
	M = [[] for i in range(h * w)]
	for i in range(h):
		for j in range(w):
			M[a[i][j] - 1] = [i, j]
	dist = [0 for i in range(h * w)]
	for i in range(h * w):
		if i - d >= 0:
			dist[i] += dist[i - d] + abs(M[i][0] - M[i - d][0]) + abs(M[i][1] - M[i - d][1])
	q = int(input())
	for i in range(q):
		(l, r) = map(int, input().split())
		print(dist[r - 1] - dist[l - 1])

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.readline
(h, w, d) = map(int, input().split())
A = [0] * (h * w)
for i in range(h):
	l = list(map(int, input().split()))
	for j in range(w):
		A[l[j] - 1] = [i, j]
q = int(input())
l = [0] * q
r = [0] * q
for i in range(q):
	(l[i], r[i]) = map(int, input().split())
ans = [0] * (h * w)
for i in range(d, h * w):
	ans[i] = ans[i - d] + abs(A[i][0] - A[i - d][0]) + abs(A[i][1] - A[i - d][1])
for i in range(q):
	print(ans[r[i] - 1] - ans[l[i] - 1])


def main():
	import sys
	read = sys.stdin.buffer.read
	readline = sys.stdin.buffer.readline
	readlines = sys.stdin.buffer.readlines
	sys.setrecursionlimit(10 ** 7)
	from collections import defaultdict
	from itertools import accumulate
	(h, w, d) = list(map(int, readline().split()))
	dict = defaultdict(list)
	memo = [[0] for _ in range(d + 1)]
	for i in range(h):
		a = list(map(int, readline().split()))
		for (j, aa) in enumerate(a):
			dict[aa] = [i, j]
	for i in range(1, d + 1):
		bf = i
		for af in range(i + d, h * w + 1, d):
			memo[i].append(abs(dict[bf][0] - dict[af][0]) + abs(dict[bf][1] - dict[af][1]))
			bf = af
		memo[i] = list(accumulate(memo[i]))
	q = int(readline())
	for _ in range(q):
		(l, r) = list(map(int, readline().split()))
		if r < l:
			(r, l) = (l, r)
		(l, i) = divmod(l, d)
		r //= d
		if i == 0:
			i = d
			l -= 1
			r -= 1
		print(memo[i][r] - memo[i][l])

def __starting_point():
	main()
__starting_point()


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
d = [[0, 0, 0] for _ in range(H * W + 2)]
for h in range(H):
	for w in range(W):
		d[A[h][w] + 1] = [h + 1, w + 1, 0]
d = d[2:]
for i in range(H * W):
	if i < D:
		continue
	d[i][2] = d[i - D][2] + abs(d[i][0] - d[i - D][0]) + abs(d[i][1] - d[i - D][1])
q = int(input())
for i in range(q):
	(l, r) = map(int, input().split())
	print(d[r - 1][2] - d[l - 1][2])


(h, w, d) = map(int, input().split())
adr = [-1] * (h * w)
for i in range(h):
	a = list(map(int, input().split()))
	for j in range(w):
		adr[a[j] - 1] = [i, j]
cost = [0] * (h * w)
for i in range(d, h * w):
	cost[i] = cost[i - d] + abs(adr[i][0] - adr[i - d][0]) + abs(adr[i][1] - adr[i - d][1])
q = int(input())
ans = []
for i in range(q):
	(l, r) = map(int, input().split())
	ans.append(cost[r - 1] - cost[l - 1])
for i in ans:
	print(i)


(H, W, D) = map(int, input().split())
A = []
for i in range(H):
	temp = list(map(int, input().split()))
	for j in range(W):
		A.append([temp[j], i + 1, j + 1])
Q = int(input())
B = []
for i in range(Q):
	B.append(list(map(int, input().split())))
A.sort()
C = [0] * (H * W)
for i in range(H * W - 1, -1, -1):
	if i + D <= H * W - 1:
		C[i] = C[i + D] + abs(A[i][1] - A[i + D][1]) + abs(A[i][2] - A[i + D][2])
for i in range(Q):
	print(C[B[i][0] - 1] - C[B[i][1] - 1])


(H, W, D) = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(H)]
d = {}
for y in range(H):
	for x in range(W):
		d[A[y][x]] = (y, x)
t = [[0] * (H * W // D + 1) for _ in range(D)]
for i in range(D):
	j = 0
	if i == 0:
		j = 1
	while i + (j + 1) * D <= H * W:
		(y1, x1) = d[i + j * D]
		(y2, x2) = d[i + (j + 1) * D]
		t[i][j + 1] = abs(y1 - y2) + abs(x1 - x2)
		j += 1
	for j in range(H * W // D):
		t[i][j + 1] += t[i][j]
Q = int(input())
result = []
for _ in range(Q):
	(L, R) = list(map(int, input().split()))
	i = L % D
	result.append(t[i][(R - i) // D] - t[i][(L - i) // D])
print('\n'.join((str(i) for i in result)))


import sys
from itertools import accumulate
input = sys.stdin.readline

def dfs(H, W, D, A, Q, LR):
	position = [(-1, -1)] * (H * W + 1)
	for h in range(H):
		for w in range(W):
			position[A[h][w]] = (h, w)
	mp = [0] * (H * W + 1)
	for i in range(1, H * W + 1 - D):
		(h, w) = position[i]
		(y, x) = position[i + D]
		mp[i + D] = abs(x - w) + abs(y - h)
	for d in range(1, D + 1):
		mp[d::D] = list(accumulate(mp[d::D]))
	ans = [mp[r] - mp[l] for (l, r) in LR]
	return ans

def main():
	(H, W, D) = list(map(int, input().split()))
	A = [None] * H
	for i in range(H):
		A[i] = tuple(map(int, input().split()))
	Q = int(input())
	LR = [None] * Q
	for i in range(Q):
		LR[i] = tuple(map(int, input().split()))
	ans = [0] * Q
	ans = dfs(H, W, D, A, Q, LR)
	print('\n'.join(map(str, ans)))

def __starting_point():
	main()
__starting_point()


(h, w, D) = map(int, input().split())
a = []
for _ in range(h):
	b = list(map(int, input().split()))
	a.append(b)
d = {}
for i in range(h):
	c = a[i]
	for j in range(w):
		d[c[j]] = (i + 1, j + 1)
R_min = h * w
R_max = 1
query = []
q = int(input())
for _ in range(q):
	(l, r) = map(int, input().split())
	query.append([l, r])
	R_min = min(l, R_min)
	R_max = max(r, R_max)
cum = [0] * (h * w + 1)
for k in range(R_min, R_max - D + 1):
	prev = cum[k - 1]
	cost = abs(d[k + D][0] - d[k][0]) + abs(d[k + D][1] - d[k][1])
	cum[k + D - 1] = cost + prev
for j in range(q):
	(l, r) = (query[j][0], query[j][1])
	score = cum[r - 1] - cum[l - 1]
	print(score)


from sys import stdin

def input():
	return stdin.readline().strip()

def main():
	(h, w, d) = map(int, input().split())
	x = [0] * (h * w)
	y = x.copy()
	for i in range(h):
		a = list(map(int, input().split()))
		for j in range(w):
			x[a[j] - 1] = i
			y[a[j] - 1] = j
	cost = [[0] for _ in range(d)]
	for i in range(d, h * w):
		cost[i % d].append(cost[i % d][-1] + abs(x[i] - x[i - d]) + abs(y[i] - y[i - d]))
	ans = []
	q = int(input())
	for _ in range(q):
		(l, r) = map(int, input().split())
		l -= 1
		r -= 1
		ans.append(cost[r % d][r // d] - cost[l % d][l // d])
	for i in ans:
		print(i)
main()


def main():
	(h, w, d) = list(map(int, input().split()))
	ans = [[0] for _ in range(d)]
	s = [0] * d
	ans[0].append(0)
	dict = {}
	for i in range(h):
		for (j, a) in enumerate(list(map(int, input().split()))):
			dict[a] = (i, j)
	for i in range(1, h * w + 1 - d):
		m = i % d
		s[m] += abs(dict[i][0] - dict[i + d][0]) + abs(dict[i][1] - dict[i + d][1])
		ans[m].append(s[m])
	q = int(input())
	for _ in range(q):
		(l, r) = list(map(int, input().split()))
		m = l % d
		print(ans[m][r // d] - ans[m][l // d])

def __starting_point():
	main()
__starting_point()


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
plc = {}
for h in range(H):
	for w in range(W):
		mm = A[h][w]
		plc[mm] = (h, w)
cst = {}
for i in range(1, D + 1):
	cst[i] = 0
for i in range(D + 1, H * W + 1):
	cst[i] = cst[i - D] + abs(plc[i][0] - plc[i - D][0]) + abs(plc[i][1] - plc[i - D][1])
Q = int(input())
for i in range(Q):
	(L, R) = map(int, input().split())
	print(cst[R] - cst[L])


(H, W, D) = map(int, input().split())
A = [[int(a) for a in input().split()] for _ in range(H)]
Q = int(input())
L = [0] * (H * W + 1)
for i in range(H):
	for j in range(W):
		L[A[i][j]] = [i, j]
E = [0] * (H * W + 1)
for i in range(D + 1, H * W + 1):
	E[i] = E[i - D] + abs(L[i][0] - L[i - D][0]) + abs(L[i][1] - L[i - D][1])
for i in range(Q):
	ans = 0
	(l, r) = map(int, input().split())
	ans = E[r] - E[l]
	print(ans)


(h, w, d) = map(int, input().split())
a = []
l = [[] for i in range(h * w + 1)]
for i in range(h):
	p = [int(j) for j in input().split()]
	a.append(p)
	for j in range(w):
		l[int(p[j])].append(i)
		l[int(p[j])].append(j)
cost = [0 for i in range(h * w + 1)]
for i in range(1, h * w + 1 - d):
	cost[i + d] = cost[i] + abs(l[i + d][0] - l[i][0]) + abs(l[i][1] - l[i + d][1])
q = int(input())
lr = []
for i in range(q):
	lr = [int(j) for j in input().split()]
	print(cost[lr[1]] - cost[lr[0]])


(h, w, d) = map(int, input().split())

def dist(start, goal):
	return abs(start[0] - goal[0]) + abs(start[1] - goal[1])
D = {}
for i in range(h):
	tmp = list(map(int, input().split()))
	for j in range(w):
		D[tmp[j]] = [i, j]
q = int(input())
A = []
for _ in range(q):
	A.append(list(map(int, input().split())))
B = [0 for i in range(h * w)]
for i in range(h * w):
	if i >= d:
		B[i] = B[i - d] + dist(D[i + 1], D[i - d + 1])
for [l, r] in A:
	ans = B[r - 1] - B[l - 1]
	print(ans)


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return list(map(int, input().split()))

def LIST():
	return list(map(int, input().split()))

def ZIP(n):
	return list(zip(*(MAP() for _ in range(n))))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
from decimal import *
(H, W, D) = MAP()
A = [LIST() for _ in range(H)]
Q = INT()
LR = [LIST() for _ in range(Q)]
dic = [[] for _ in range(D)]
for y in range(H):
	for x in range(W):
		dic[A[y][x] % D].append([A[y][x], y, x])
for lis in dic:
	lis.sort(key=lambda x: x[0])
for lis in dic:
	lis[0][0] = 0
	for i in range(len(lis)):
		if i == len(lis) - 1:
			break
		point = (lis[i][1], lis[i][2])
		dist_point = (lis[i + 1][1], lis[i + 1][2])
		lis[i + 1][0] = lis[i][0] + abs(point[0] - dist_point[0]) + abs(point[1] - dist_point[1])
for (L, R) in LR:
	print(dic[R % D][ceil(R / D) - 1][0] - dic[R % D][ceil(L / D) - 1][0])


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
px = [0] * (H * W + 1)
py = [0] * (H * W + 1)
for y in range(H):
	for x in range(W):
		n = A[y][x]
		px[n] = x + 1
		py[n] = y + 1
csum = [0] * (H * W + 1)
for i in range(D + 1, H * W + 1):
	csum[i] = csum[i - D] + abs(px[i] - px[i - D]) + abs(py[i] - py[i - D])
for q in range(Q):
	(L, R) = map(int, input().split())
	print(csum[R] - csum[L])


(h, w, d) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
pos = {a[i][j]: (i, j) for i in range(h) for j in range(w)}
acc = [0] * (h * w + 1)
for v in range(d + 1, h * w + 1):
	(i, j) = pos[v]
	(x, y) = pos[v - d]
	acc[v] = acc[v - d] + abs(x - i) + abs(y - j)
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(acc[r] - acc[l])


def main():
	(H, W, D) = list(map(int, input().split()))
	A = [[0, 0] for i in range(H * W)]
	for h in range(H):
		for (w, a) in enumerate(map(int, input().split())):
			(A[~-a][0], A[~-a][1]) = (h, w)
	B = [0] * (H * W)
	for i in range(H * W - D):
		B[i + D] = B[i] + abs(A[i][0] - A[i + D][0]) + abs(A[i][1] - A[i + D][1])
	for q in range(int(input())):
		(l, r) = list(map(int, input().split()))
		print(B[~-r] - B[~-l])
main()


(H, W, D) = map(int, input().split())
A = [tuple(map(int, input().split())) for i in range(H)]
Q = int(input())
LR = [tuple(map(int, input().split())) for i in range(Q)]
pos = [None] * (H * W)
for (i, row) in enumerate(A):
	for (j, a) in enumerate(row):
		pos[a - 1] = (i, j)
cums = [0] * D
for ((x1, y1), (x2, y2)) in zip(pos, pos[D:]):
	d = abs(x1 - x2) + abs(y1 - y2)
	cums.append(cums[-D] + d)
ans = []
for (l, r) in LR:
	ans.append(cums[r - 1] - cums[l - 1])
print(*ans, sep='\n')


(h, w, d) = map(int, input().split())
a = {}
for y in range(h):
	line = list(map(int, input().split()))
	for x in range(len(line)):
		a[line[x] - 1] = (y, x)
num = len(a)
dp = [0] * num
for i in range(num - 1, -1, -1):
	if i + d <= num - 1:
		(x, y) = a[i]
		(px, py) = a[i + d]
		dp[i] = dp[i + d] + abs(x - px) + abs(y - py)
q = int(input())
for _ in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	print(dp[l] - dp[r])


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for _ in [0] * H]
Q = int(input())
LR = [list(map(int, input().split())) for _ in [0] * Q]
n_xy = [0] * (H * W)
for (i, row) in enumerate(A):
	for (j, a) in enumerate(row):
		n_xy[a - 1] = [i, j]
S = [0] * (H * W)
for i in range(D, H * W):
	S[i] = S[i - D] + abs(n_xy[i][0] - n_xy[i - D][0]) + abs(n_xy[i][1] - n_xy[i - D][1])
for (L, R) in LR:
	print(S[R - 1] - S[L - 1])


(h, w, d) = map(int, input().split())
a = []
dict = {}
for i in range(h):
	b = list(map(int, input().split()))
	for j in range(w):
		dict[b[j]] = [i, j]
dist = [0 for i in range(h * w)]
for i in range(1, h * w - d + 1):
	dist[i - 1] = abs(dict[i + d][1] - dict[i][1]) + abs(dict[i + d][0] - dict[i][0])
for i in range(h * w - d - 1, -1, -1):
	dist[i] += dist[i + d]
q = int(input())
for i in range(q):
	(l, r) = map(int, input().split())
	ans = dist[l - 1] - dist[r - 1]
	print(ans)


(h, w, d) = map(int, input().split())
l = [[0]] * (h * w + 1)
for i in range(h):
	temp = list(map(int, input().split()))
	for j in range(len(temp)):
		l[temp[j]] = [i + 1, j + 1]
c = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
	(pi, pj) = l[i]
	(qi, qj) = l[i - d]
	c[i] = c[i - d] + abs(pi - qi) + abs(pj - qj)
q = int(input())
for i in range(q):
	(l, r) = map(int, input().split())
	print(c[r] - c[l])


(h, w, d) = map(int, input().split())
n = h * w
a = [None for i in range(n)]
for i in range(h):
	inp = list(map(int, input().split()))
	for j in range(w):
		a[inp[j] - 1] = (i, j)
dst = [0 for i in range(d)]
for i in range(d, n):
	dst.append(abs(a[i - d][0] - a[i][0]) + abs(a[i - d][1] - a[i][1]))
s = [0 for i in range(d)]
for i in range(d, n):
	s.append(s[i - d] + dst[i])
q = int(input())
for i in range(q):
	(l, r) = map(int, input().split())
	print(s[r - 1] - s[l - 1])


import sys
input = sys.stdin.readline
(h, w, d) = list(map(int, input().split()))
n = h * w
a = [0] * n
for i in range(h):
	t = list(map(int, input().split()))
	for j in range(w):
		a[w * i + j] = t[j] - 1

def dist(i, j):
	dh = abs(i // w - j // w)
	dw = abs(i % w - j % w)
	return dh + dw
idx_list = [0] * n
for i in range(n):
	idx_list[a[i]] = i
dist_list = [0] * n
for i in range(n):
	if i < d:
		dist_list[i] = 0
	else:
		dist_list[i] = dist_list[i - d] + dist(idx_list[i - d], idx_list[i])
q = int(input())
for i in range(q):
	(l, r) = list(map(int, input().split()))
	l -= 1
	r -= 1
	print(dist_list[r] - dist_list[l])


(h, w, d) = map(int, input().split())
b = [0] * (h * w)
for i in range(h):
	for (j, s) in enumerate(input().split()):
		b[int(s) - 1] = (i, j)
a = [0] * (h * w + d)
for i in range(d, h * w):
	a[i] = a[i - d] + abs(b[i][0] - b[i - d][0]) + abs(b[i][1] - b[i - d][1])
for i in range(int(input())):
	(l, r) = map(int, input().split())
	print(a[r - 1] - a[l - 1])


(H, W, D) = map(int, input().split())
M = [(-1, -1)] * (H * W + 1)
A = []
for i in range(H):
	As = list(map(int, input().split()))
	for j in range(W):
		a = As[j]
		M[a] = (i, j)
	A.append(As)
Dist = [0] * (H * W + 1)
for k in range(0, H * W - D + 1):
	(i, j) = M[k]
	(x, y) = M[k + D]
	Dist[k + D] = Dist[k] + abs(x - i) + abs(y - j)
Q = int(input())
for i in range(Q):
	(L, R) = map(int, input().split())
	r = Dist[R] - Dist[L]
	print(r)


(h, w, d) = (int(i) for i in input().split())
num = [None for i in range(h * w)]
for i in range(h):
	a = list(map(int, input().split()))
	for j in range(w):
		num[a[j] - 1] = (i, j)
numm = [None for i in range(h * w)]
for i in range(d):
	numm[i] = 0
for i in range(d, h * w):
	numm[i] = numm[i - d] + abs(num[i][0] - num[i - d][0]) + abs(num[i][1] - num[i - d][1])
q = int(input())
for i in range(q):
	(l, r) = list(map(int, input().split()))
	print(numm[r - 1] - numm[l - 1])


(H, W, D) = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(H)]
inv_A = [(0, 0)] * (H * W + 1)
for (y, a) in enumerate(A):
	for (x, a_) in enumerate(a):
		inv_A[a_] = (y, x)
C = [0] * D
c = 0
for i in range(D, H * W + 1):
	(y1, x1) = inv_A[i]
	(y2, x2) = inv_A[i - D]
	C.append(abs(y1 - y2) + abs(x1 - x2) + C[i - D])
Ans = []
Q = int(input())
for _ in range(Q):
	(l, r) = list(map(int, input().split()))
	Ans.append(C[r] - C[l])
print('\n'.join(map(str, Ans)))


(h, w, d) = map(int, input().split())
ad = {}
for i in range(h):
	line = list(map(int, input().split()))
	for j in range(w):
		ad[line[j]] = (i, j)
q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]
cl = [0] * (h * w + 1)
for i in range(1, h * w + 1):
	if i + d < len(cl):
		f = ad[i]
		t = ad[i + d]
		cl[i + d] = cl[i] + abs(f[0] - t[0]) + abs(f[1] - t[1])
for (l, r) in lr:
	print(cl[r] - cl[l])


(H, W, D) = list(map(int, input().split()))

def main():
	A = list()
	for h in range(H):
		for (w, a) in enumerate(map(int, input().split())):
			A.append([a, h, w])
	A = sorted(A, key=lambda x: x[0])
	B = [0] * (H * W)
	for i in range(D):
		while i + D < W * H:
			B[i + D] = B[i] + abs(A[i][1] - A[i + D][1]) + abs(A[i][2] - A[i + D][2])
			i += D
	for q in range(int(input())):
		(l, r) = list(map(int, input().split()))
		print(B[~-r] - B[~-l])
main()


(H, W, D) = map(int, input().split())
A = [0] * H
for i in range(H):
	A[i] = list(map(int, input().split()))
dict = {}
for i in range(H):
	for j in range(W):
		dict[A[i][j]] = [i, j]
dp = [0] * (H * W + 1)
for k in range(D + 1, H * W + 1):
	dp[k] = dp[k - D] + abs(dict[k][0] - dict[k - D][0]) + abs(dict[k][1] - dict[k - D][1])
Q = int(input())
for i in range(Q):
	(L, R) = map(int, input().split())
	print(dp[R] - dp[L])


(H, W, D) = map(int, input().split())
px = [0] * (H * W + 1)
py = [0] * (H * W + 1)
d = [0] * (H * W + 1)
for y in range(H):
	line = list(map(int, input().split()))
	for (x, A) in enumerate(line):
		px[A] = x
		py[A] = y
for i in range(D + 1, H * W + 1):
	d[i] = d[i - D] + abs(px[i] - px[i - D]) + abs(py[i] - py[i - D])
Q = int(input())
for _ in range(Q):
	(L, R) = map(int, input().split())
	print(d[R] - d[L])


from collections import defaultdict
(H, W, D) = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]
d = defaultdict(list)
for i in range(H):
	for j in range(W):
		d[A[i][j]].append([i, j])
p = []
for s in range(1, D + 1):
	c = 0
	q = [0]
	for i in range(s + D, H * W + 1, D):
		(i0, j0) = d[i - D][0]
		(i1, j1) = d[i][0]
		c += abs(i0 - i1) + abs(j0 - j1)
		q.append(c)
	p.append(q)
for (l, r) in LR:
	i = l % D - 1
	s = (l - 1) // D
	e = (r - 1) // D
	print(p[i][e] - p[i][s])


(h, w, d) = map(int, input().split())
pos = [(0, 0) for _ in range(h * w)]
for i in range(h):
	for (j, a) in enumerate(input().split()):
		pos[int(a) - 1] = (i, j)
q = int(input())
distances = [0 for _ in range(h * w)]
for i in range(d, h * w):
	a = h * w - i
	(i, j) = pos[a - 1]
	(x, y) = pos[a + d - 1]
	distances[a - 1] = distances[a + d - 1] + abs(i - x) + abs(j - y)
for _ in range(q):
	(l, r) = map(int, input().split())
	print(distances[l - 1] - distances[r - 1])


(h, w, d) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
dic = [0] * (h * w)
for i in range(h):
	for j in range(w):
		dic[a[i][j] - 1] = (i, j)
sup = [0] * (h * w)
for x in range(d, h * w):
	sup[x] = sup[x - d] + abs(dic[x][0] - dic[x - d][0]) + abs(dic[x][1] - dic[x - d][1])
q = int(input())
for _ in range(q):
	(l, r) = map(int, input().split())
	print(sup[r - 1] - sup[l - 1])


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [None] * (H * W)
C = [0] * (H * W)
for (h, aa) in enumerate(A):
	for (w, a) in enumerate(aa):
		B[a - 1] = (h, w)
for i in range(H * W - D):
	C[i + D] = C[i] + abs(B[i][0] - B[i + D][0]) + abs(B[i][1] - B[i + D][1])
for _ in range(int(input())):
	(L, R) = map(int, input().split())
	print(C[R - 1] - C[L - 1])


import sys
input = sys.stdin.readline
(h, w, d) = map(int, input().split())
p = dict()
for i in range(h):
	for (j, x) in enumerate(map(int, input().split())):
		p[x] = (i, j)
dp = [0] * (h * w + 1)
for i in range(h * w + 1):
	if d < i:
		dp[i] = dp[i - d] + abs(p[i][0] - p[i - d][0]) + abs(p[i][1] - p[i - d][1])
q = int(input())
for i in range(q):
	(a, b) = map(int, input().split())
	ans = dp[b] - dp[a]
	print(ans)


(H, W, D) = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(H)]
P = {}
for h in range(H):
	for w in range(W):
		P[A[h][w]] = (h, w)
C = [0] * (H * W + 1)
for i in range(D + 1, H * W + 1):
	C[i] = C[i - D] + abs(P[i][0] - P[i - D][0]) + abs(P[i][1] - P[i - D][1])
Q = int(input())
for q in range(Q):
	(L, R) = list(map(int, input().split()))
	print(C[R] - C[L])


(h, w, d) = map(int, input().split())
g = [[] for _ in range(w)]
for _ in range(h):
	tmp_list = list(map(int, input().split()))
	for i in range(w):
		g[i].append(tmp_list[i])
q = int(input())
qs = [list(map(int, input().split())) for _ in range(q)]
loc = [0] * (h * w + 1)
for i in range(h):
	for j in range(w):
		loc[g[j][i]] = (i, j)
roots = [0] * (h * w + 1)
for i in range(1, d + 1):
	j = i + d
	while j < h * w + 1:
		cost = abs(loc[j][0] - loc[j - d][0]) + abs(loc[j][1] - loc[j - d][1])
		roots[j] = cost + roots[j - d]
		j += d
for i in qs:
	(l, r) = (i[0], i[1])
	print(roots[r] - roots[l])


import sys
input = sys.stdin.readline
(h, w, d) = map(int, input().split())
num = h * w
x = [0] * (num + 1)
y = [0] * (num + 1)
mp = [0] * (num + 1)
for i in range(h):
	for (j, a) in enumerate(map(int, input().split())):
		(x[a], y[a]) = [i + 1, j + 1]
for i in range(d + 1, num + 1):
	mp[i] = mp[i - d] + abs(x[i] - x[i - d]) + abs(y[i] - y[i - d])
q = int(input())
for _ in range(q):
	(l, r) = map(int, input().split())
	print(mp[r] - mp[l])


def main():
	import sys
	input = sys.stdin.readline
	(H, W, D) = [int(x) for x in input().strip().split()]
	M = [0] * H
	C = {}
	revM = {}
	for h in range(H):
		M[h] = [int(x) for x in input().strip().split()]
		for (i, w) in enumerate(M[h]):
			revM[w] = (h, i)
	Q = int(input())
	HW = H * W
	ans = [0] * (HW + 1)
	for i in range(1, D + 1):
		cur = i
		while cur + D <= HW:
			ans[cur + D] += ans[cur] + abs(revM[cur][0] - revM[cur + D][0]) + abs(revM[cur][1] - revM[cur + D][1])
			cur += D
	for q in range(Q):
		(l, r) = [int(x) for x in input().strip().split()]
		print(ans[r] - ans[l])

def __starting_point():
	main()
__starting_point()


(H, W, D) = map(int, input().split())
pos = {}
for i in range(H):
	A = list(map(int, input().split()))
	for j in range(W):
		pos[A[j]] = (i, j)
p = [0] * (H * W + 1)
for i in range(D + 1, H * W + 1):
	p[i] = p[i - D] + abs(pos[i][0] - pos[i - D][0]) + abs(pos[i][1] - pos[i - D][1])
Q = int(input())
for _ in range(Q):
	(L, R) = map(int, input().split())
	print(p[R] - p[L])


(H, W, D) = map(int, input().split())
A = {}
for i in range(H):
	row = list(map(int, input().split()))
	for j in range(W):
		A[row[j]] = [i + 1, j + 1]
Q = int(input())
ANS = [0] * (H * W + 1)
for i in range(D + 1, H * W + 1):
	ANS[i] = ANS[i - D] + abs(A[i][0] - A[i - D][0]) + abs(A[i][1] - A[i - D][1])
for _ in range(Q):
	(L, R) = map(int, input().split())
	print(ANS[R] - ANS[L])


(h, w, d) = map(int, input().split())
m = {}
for i in range(1, h + 1):
	for (j, k) in enumerate(map(int, input().split())):
		m[k] = (i, j + 1)
s = [0 for _ in range(1 + h * w)]
for i in range(d + 1, 1 + h * w):
	s[i] = s[i - d] + abs(m[i][0] - m[i - d][0]) + abs(m[i][1] - m[i - d][1])
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(s[b] - s[a])


(H, W, D) = map(int, input().split())
p = {}
for i in range(H):
	for (j, value) in enumerate(map(int, input().split())):
		p[value] = (i, j)
cost = {}
for i in range(1, W * H + 1):
	cost[i] = cost[i - D] + abs(p[i][0] - p[i - D][0]) + abs(p[i][1] - p[i - D][1]) if i > D else 0
Q = int(input())
for _ in range(Q):
	(L, R) = map(int, input().split())
	print(cost[R] - cost[L])


(h, w, d) = map(int, input().split())
l = [[] for t in range(h * w)]
for i in range(h):
	ll = list(map(int, input().split()))
	for j in range(w):
		l[ll[j] - 1] = [i, j]
r = [[0] for dd in range(d)]
for dd in range(d):
	if dd == 0:
		k = d
	else:
		k = dd
	while k + d <= h * w:
		r[dd].append(r[dd][-1] + abs(l[k + d - 1][0] - l[k - 1][0]) + abs(l[k + d - 1][1] - l[k - 1][1]))
		k += d
q = int(input())
for qq in range(q):
	(a, b) = map(int, input().split())
	if a % d == 0:
		p = d
	else:
		p = a % d
	aa = (a - p) // d
	bb = (b - p) // d
	ans = r[a % d][bb] - r[a % d][aa]
	print(ans)


import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
	(H, W, D) = list(map(int, input().split()))
	A = [list(map(int, input().split())) for _ in range(H)]
	x = [0] * (H * W + 1)
	p = [[] for _ in range(H * W + 1)]
	for h in range(H):
		for w in range(W):
			p[A[h][w]] = [h, w]
	for i in range(D + 1, H * W + 1):
		x[i] = x[i - D] + abs(p[i][0] - p[i - D][0]) + abs(p[i][1] - p[i - D][1])
	for _ in range(int(input())):
		(l, r) = list(map(int, input().split()))
		print(x[r] - x[l])

def __starting_point():
	main()
__starting_point()


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
Q = int(input())
S = [list(map(int, input().split())) for i in range(Q)]
P = [None] * (H * W + 1)
for i in range(H):
	for j in range(W):
		P[A[i][j]] = [i, j]
Accum = [0] * (H * W + 1)
accum = 0
for i in range(D + 1, H * W + 1):
	Accum[i] = Accum[i - D] + abs(P[i][0] - P[i - D][0]) + abs(P[i][1] - P[i - D][1])
for s in S:
	print(Accum[s[1]] - Accum[s[0]])


dic = {}
(h, w, d) = map(int, input().split())
lis = [list(input().split()) for _ in range(h)]
for i in range(h):
	for j in range(w):
		dic[int(lis[i][j])] = (i, j)
n = h * w
su = [0] * (n + 1)
for k in range(1, n - d + 1):
	x = dic[k + d][0] - dic[k][0]
	y = dic[k + d][1] - dic[k][1]
	su[k + d] = su[k] + abs(x) + abs(y)
q = int(input())
for i in range(q):
	(s, g) = map(int, input().split())
	print(su[g] - su[s])


(h, w, d) = map(int, input().split())
ans = [0 for _ in range(h * w + 1)]
za = [[] for _ in range(h * w + 1)]
for i in range(h):
	a = list(map(int, input().split()))
	for x in range(w):
		za[a[x]].append(i)
		za[a[x]].append(x)
for x in range(1, h * w + 1):
	if x + d <= w * h:
		ans[x + d] = ans[x] + abs(za[x + d][0] - za[x][0]) + abs(za[x + d][1] - za[x][1])
q = int(input())
for _ in range(q):
	(e, f) = map(int, input().split())
	print(ans[f] - ans[e])


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for _ in [0] * H]
Q = int(input())
LR = [list(map(int, input().split())) for _ in [0] * Q]
N = H * W
C = [0] * N
pos = [(0, 0)] * N
for i in range(H):
	for j in range(W):
		a = A[i][j] - 1
		pos[a] = (i, j)
for i in range(D, N):
	C[i] = sum((abs(pos[i][xy] - pos[i - D][xy]) for xy in range(2)))
S = [0] * (N + 1)
for i in range(D, N + 1):
	S[i] = C[i - 1] + S[i - D]
for (l, r) in LR:
	print(S[r] - S[l])


(h, w, d) = map(int, input().split())
coordinates = {}
for i in range(h):
	row = list(map(int, input().split()))
	for j in range(w):
		coordinates[row[j]] = (i, j)
costs = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
	(x1, y1) = coordinates[i]
	(x2, y2) = coordinates[i - d]
	costs[i] = abs(x1 - x2) + abs(y1 - y2) + costs[i - d]
q = int(input())
for _ in range(q):
	(l, r) = map(int, input().split())
	print(costs[r] - costs[l])


(H, W, D) = map(int, input().split())
A = [tuple(map(int, input().split())) for _ in range(H)]
P = {}
for i in range(H):
	for j in range(W):
		P[A[i][j] - 1] = (i, j)
cum = [0] * (H * W + 1)
for a in range(H * W - D):
	(i, j) = P[a]
	(x, y) = P[a + D]
	cum[a + D] = cum[a] + abs(x - i) + abs(y - j)
Q = int(input())
ans = []
for _ in range(Q):
	(l, r) = map(int, input().split())
	ans.append(cum[r - 1] - cum[l - 1])
print('\n'.join(map(str, ans)))


(H, W, D) = map(int, input().split())
dic = dict()
for i in range(H):
	A = list(map(int, input().split()))
	for j in range(W):
		dic[A[j]] = (i, j)
Q = int(input())
d = [0 for i in range(H * W + 1)]
for i in range(D + 1, H * W + 1):
	(p, q) = dic[i - D]
	(x, y) = dic[i]
	d[i] = d[i - D] + abs(p - x) + abs(q - y)
for _ in range(Q):
	ans = 0
	(L, R) = map(int, input().split())
	print(d[R] - d[L])


(H, W, D) = map(int, input().split())
m = [None] * (H * W + 1)
s = [0] * (H * W + 1)
for y in range(H):
	A = list(map(int, input().split()))
	for (x, a) in enumerate(A):
		m[a] = (x, y)
for i in range(D + 1, H * W + 1):
	(x, y) = m[i]
	(px, py) = m[i - D]
	s[i] = s[i - D] + abs(x - px) + abs(y - py)
Q = int(input())
for i in range(Q):
	(L, R) = map(int, input().split())
	print(s[R] - s[L])


(h, w, d) = map(int, input().split())
l = [list(map(int, input().split())) for i in range(h)]
L = [0 for i in range(h * w)]
for i in range(h):
	for j in range(w):
		L[l[i][j] - 1] = [i, j]
sumL = [0 for i in range(h * w + 1)]
for i in range(h * w):
	if i >= d:
		sumL[i + 1] = sumL[i + 1 - d] + abs(L[i][0] - L[i - d][0]) + abs(L[i][1] - L[i - d][1])
q = int(input())
QL = [list(map(int, input().split())) for i in range(q)]
for i in range(q):
	print(sumL[QL[i][1]] - sumL[QL[i][0]])


import math, itertools, fractions, heapq, collections, bisect, sys, queue, copy
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def LS():
	return sys.stdin.readline().split()

def S():
	return input()

def main():
	(h, w, d) = LI()
	l = [LI() for _ in range(h)]
	q = I()
	ql = [LI() for _ in range(q)]
	dic = {}
	for i in range(h):
		for j in range(w):
			x = l[i][j]
			dic[x] = (i + 1, j + 1)
	n = h * w
	to_last_distance = [0] * n
	for i in range(1, n + 1)[::-1]:
		if i + d <= n:
			(i_y, i_x) = dic[i]
			(ipd_y, ipd_x) = dic[i + d]
			to_last_distance[i - 1] = to_last_distance[i + d - 1]
			to_last_distance[i - 1] += abs(i_y - ipd_y) + abs(i_x - ipd_x)
	ans = []
	for (st, ed) in ql:
		ans.append(to_last_distance[st - 1] - to_last_distance[ed - 1])
	for x in ans:
		print(x)
main()


(H, W, D) = map(int, input().split())
A = []
N = H * W
indices = [None] * (N + 1)
for h in range(H):
	tmp = list(map(int, input().split()))
	A.append(tmp)
	for w in range(W):
		indices[tmp[w]] = (h, w)
d = [0] * (N + 1)
for i in range(D + 1, N + 1):
	(y1, x1) = indices[i]
	(y2, x2) = indices[i - D]
	d[i] = d[i - D] + abs(y1 - y2) + abs(x1 - x2)
Q = int(input())
for _ in range(Q):
	(l, r) = map(int, input().split())
	print(d[r] - d[l])


(H, W, D) = list(map(int, input().split()))
d = {}
for i in range(1, H + 1):
	A = list(map(int, input().split()))
	for j in range(W):
		d[A[j]] = (i, j + 1)
acc = [[] for _ in range(D)]
for i in range(1, D + 1):
	acc[i - 1].append(0)
	for j in range(i, H * W + 1 - D, D):
		(x, y) = d[j]
		(a, b) = d[j + D]
		acc[i - 1].append(acc[i - 1][-1] + abs(a - x) + abs(b - y))
Q = int(input())
for _ in range(Q):
	(l, r) = list(map(int, input().split()))
	print(acc[(l - 1) % D][(r - 1) // D] - acc[(l - 1) % D][(l - 1) // D])


import sys
(H, W, D) = map(int, sys.stdin.readline().split())
num = {}
for j in range(H):
	tmp = map(int, sys.stdin.readline().split())
	for (i, n) in enumerate(tmp):
		num[n] = (i, j)
S = [0 for _ in range(H * W + D)]
for i in range(D + 1, H * W + 1):
	(x, y) = num[i]
	(a, b) = num[i - D]
	S[i] = S[i - D] + abs(x - a) + abs(y - b)
Q = int(sys.stdin.readline())
for _ in range(Q):
	(L, R) = map(int, sys.stdin.readline().split())
	r = L % D
	print(S[R] - S[L])


(h, w, d) = map(int, input().split())
pos = [-1 for _ in range(h * w)]
for i in range(h):
	alst = list(map(int, input().split()))
	for (j, a) in enumerate(alst):
		pos[a - 1] = [i, j]
dif = [0 for _ in range(h * w)]
check = [False for _ in range(h * w)]
for num in range(h * w):
	if check[num]:
		continue
	check[num] = True
	total = 0
	dif[num] = total
	for j in range(num + d, h * w, d):
		dx = pos[j][0] - pos[j - d][0]
		dy = pos[j][1] - pos[j - d][1]
		dd = abs(dx) + abs(dy)
		total += dd
		dif[j] = total
		check[j] = True
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	print(abs(dif[l] - dif[r]))


(H, W, D) = map(int, input().split())
pos = [0] * (H * W)
Z = [0] * (H * W + 1)
for j in range(H):
	A = list(map(int, input().split()))
	for i in range(W):
		pos[A[i] - 1] = (i, j)
for k in range(D):
	for x in range(k, H * W - D, D):
		pos1 = pos[x]
		pos2 = pos[x + D]
		Z[x + D + 1] = abs(pos2[0] - pos1[0]) + abs(pos2[1] - pos1[1]) + Z[x + 1]
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	print(Z[y] - Z[x])


from collections import defaultdict
(H, W, D) = list(map(int, input().split()))
grid = [[0] * W for _ in range(H)]
for h in range(H):
	grid[h] = list(map(int, input().split()))
number_yx = [[0, 0] for _ in range(H * W + 1)]
for y in range(H):
	for x in range(W):
		number_yx[grid[y][x]] = [y, x]
fromto_cost = defaultdict(lambda : defaultdict(int))
for mod_group in range(D):
	start = mod_group + 1
	previous = start
	fromto_cost[start][start] = 0
	(previous_y, previous_x) = number_yx[previous]
	cost = 0
	while previous + D <= H * W:
		Next = previous + D
		(Next_y, Next_x) = number_yx[Next]
		cost += abs(Next_y - previous_y) + abs(Next_x - previous_x)
		fromto_cost[start][Next] = cost
		previous = Next
		(previous_y, previous_x) = (Next_y, Next_x)
Q = int(input())
ans_ls = [0] * Q
for i in range(Q):
	(start, goal) = list(map(int, input().split()))
	mod = start % D
	base = mod
	if base == 0:
		base = D
	base_to_goal = fromto_cost[base][goal]
	base_to_start = fromto_cost[base][start]
	ans_ls[i] = base_to_goal - base_to_start
for ans in ans_ls:
	print(ans)


import sys
read = sys.stdin.buffer.read
inp = iter(map(int, read().split()))
(H, W, D) = (next(inp), next(inp), next(inp))
addr = [None] * (H * W + 1)
for i in range(H):
	for j in range(W):
		v = next(inp)
		addr[v] = (i, j)
cost = []
for m in range(D):
	arr = [0]
	for x in range((H * W - m) // D):
		if m + x * D == 0:
			arr.append(0)
			continue
		(r, c) = addr[m + x * D]
		(nr, nc) = addr[m + (x + 1) * D]
		arr.append(arr[-1] + abs(nr - r) + abs(nc - c))
	cost.append(arr)
Q = next(inp)
for _ in range(Q):
	(s, t) = (next(inp), next(inp))
	m = s % D
	ans = cost[m][t // D] - cost[m][s // D]
	print(ans)


(h, w, d) = map(int, input().split())
p = [0] * (h * w + d * 2)
s = [0] * (h * w + d * 2)
for x in range(h):
	y = 1
	for a in map(int, input().split()):
		p[a] = [x, y]
		y += 1
for i in range(1, h * w + 1 - d):
	s[i + d] = s[i] + abs(p[i + d][0] - p[i][0]) + abs(p[i + d][1] - p[i][1])
for i in range(int(input())):
	(l, r) = map(int, input().split())
	print(s[r] - s[l])


(h, w, d) = map(int, input().split())
p = [[] for _ in range(h * w)]
for i in range(h):
	temp = list(map(int, input().split()))
	for j in range(w):
		p[temp[j] - 1] = [i, j]
q = int(input())
a = [[int(x) - 1 for x in input().split()] for _ in range(q)]
s = [0 for _ in range(h * w)]
for i in range(d, h * w):
	s[i] = s[i - d] + abs(p[i][0] - p[i - d][0]) + abs(p[i][1] - p[i - d][1])
for i in range(q):
	print(s[a[i][1]] - s[a[i][0]])


(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)]
d = [0] * (H * W + 1)
num_dict = {}
y = 0
for aa in A:
	x = 0
	for a in aa:
		num_dict[a] = [x, y]
		x += 1
	y += 1
for i in range(D + 1, H * W + 1):
	d[i] = d[i - D] + abs(num_dict[i][0] - num_dict[i - D][0]) + abs(num_dict[i][1] - num_dict[i - D][1])
for (l, r) in LR:
	print(d[r] - d[l])


(h, w, d) = map(int, input().split())
c = {}
for i in range(h):
	x = list(map(int, input().split()))
	for j in range(w):
		c[x[j]] = [i, j]
a = [0] * (h * w - d + 1)
b = [0] * (h * w + 1)
for k in range(1, h * w - d + 1):
	a[k] = abs(c[k + d][0] - c[k][0]) + abs(c[k + d][1] - c[k][1])
for k in range(1, h * w - d + 1):
	if k <= d:
		b[k + d] = a[k]
	else:
		b[k + d] = b[k] + a[k]
for _ in [0] * int(input()):
	(l, r) = map(int, input().split())
	print(b[r] - b[l])


import sys
input = sys.stdin.readline
(h, w, d) = map(int, input().split())
ahw = [0] * (h * w)
dp = [0] * (h * w)
for i in range(h):
	temp = [int(i) - 1 for i in input().split()]
	for j in range(w):
		ahw[temp[j]] = (i, j)
for i in range(d):
	dp[i] = 0
for i in range(d, h * w):
	dp[i] = dp[i - d] + abs(ahw[i][0] - ahw[i - d][0]) + abs(ahw[i][1] - ahw[i - d][1])
q = int(input())
for i in range(q):
	(l, r) = map(int, input().split())
	print(dp[r - 1] - dp[l - 1])


(H, W, D) = map(int, input().split())
data = [0] * (H * W + D + 1)
for i in range(H):
	A = list(map(int, input().split()))
	for j in range(W):
		data[A[j] + D] = [i, j]
Q = int(input())
S = [0] * (H * W + D + 1)
for i in range(H * W):
	if i >= D:
		S[i + D + 1] = S[i + 1] + abs(data[i + D + 1][0] - data[i + 1][0]) + abs(data[i + D + 1][1] - data[i + 1][1])
for i in range(Q):
	(L, R) = map(int, input().split())
	print(S[R + D] - S[L + D])


(h, w, d) = map(int, input().split())
lst = [0 for i in range(h * w + 1)]
for i in range(h):
	x = list(map(int, input().split()))
	for j in range(w):
		lst[x[j]] = (i, j)
dif = [0 for i in range(h * w + 1)]
i = d + 1
while i <= w * h:
	dif[i] = dif[i - d] + abs(lst[i][0] - lst[i - d][0]) + abs(lst[i][1] - lst[i - d][1])
	i += 1
q = int(input())
ans = []
for i in range(q):
	(l, r) = map(int, input().split())
	ans.append(dif[r] - dif[l])
for num in ans:
	print(num)


(h, w, d) = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(h)]
pos = [0] * (h * w + 1)
for i in range(h):
	for j in range(w):
		pos[a[i][j]] = (j, i)
dis = [0] * (h * w + 1)
for i in range(h * w + 1):
	if i > d:
		(x1, y1) = pos[i - d]
		(x2, y2) = pos[i]
		dis[i] = abs(x1 - x2) + abs(y1 - y2) + dis[i - d]
res = []
q = int(input())
for i in range(q):
	(l, r) = list(map(int, input().split()))
	res.append(dis[r] - dis[l])
print('\n'.join(map(str, res)))


import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate
sys.setrecursionlimit(10 ** 6)
INF = 10 ** 12
m = 10 ** 9 + 7

def main():
	(H, W, D) = list(map(int, input().split()))
	A = [None] * (H * W)
	for i in range(H):
		s = list(map(int, input().split()))
		for j in range(W):
			A[s[j] - 1] = (i, j)
	costs = [0] * (H * W)
	for i in range(D):
		j = H * W - 1 - i
		while j - D >= 0:
			costs[j - D] = costs[j] + abs(A[j][0] - A[j - D][0]) + abs(A[j][1] - A[j - D][1])
			j -= D
	Q = int(input())
	for i in range(Q):
		(L, R) = [int(x) - 1 for x in input().split()]
		print(costs[L] - costs[R])

def __starting_point():
	main()
__starting_point()


(h, w, d) = map(int, input().split())
px = [0] * (h * w + 1)
py = [0] * (h * w + 1)
for i in range(h):
	l = list(map(int, input().split()))
	for j in range(w):
		(px[l[j]], py[l[j]]) = (i, j)
count = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
	count[i] = count[i - d] + abs(px[i] - px[i - d]) + abs(py[i] - py[i - d])
n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	print(count[b] - count[a])


(h, w, d) = map(int, input().split())
xy = [(0, 0)] * (h * w + 1)
for i in range(h):
	a = list(map(int, input().split()))
	for j in range(w):
		xy[a[j]] = (i + 1, j + 1)
s = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
	s[i] = abs(xy[i][0] - xy[i - d][0]) + abs(xy[i][1] - xy[i - d][1]) + s[i - d]
q = int(input())
for _ in range(q):
	(l, r) = map(int, input().split())
	print(s[r] - s[l])


(h, w, d) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
b = [[0, 0] for i in range(h * w + 1)]
for i in range(h):
	for j in range(w):
		b[a[i][j]] = [i, j]
c = [0] * d
for i in range(len(b) - d):
	c.append(abs(b[i + d][0] - b[i][0]) + abs(b[i + d][1] - b[i][1]) + c[-d])
q = int(input())
for i in range(q):
	(l, r) = map(int, input().split())
	print(c[r] - c[l])


n = 0
(h, w, d) = map(int, input().split())
x = [0] * (h * w)
y = [0] * (h * w)
for i in range(h):
	for a in input().split():
		A = int(a) - 1
		x[A] = n % w
		y[A] = n // w
		n += 1
c = [0] * (h * w)
for i in range(h * w):
	if i >= d:
		c[i] = c[i - d] + abs(x[i] - x[i - d]) + abs(y[i] - y[i - d])
q = int(input())
for i in range(q):
	(l, r) = map(int, input().split())
	print(c[r - 1] - c[l - 1])


(h, w, d) = list(map(int, input().split()))
index = [-1] * (h * w)
for i in range(h):
	a = list(map(int, input().split()))
	for j in range(len(a)):
		index[a[j] - 1] = (i + 1, j + 1)
data = [[] for _ in range(d)]
for i in range(1, d + 1):
	num = i
	(x, y) = index[num - 1]
	data[i - 1].append(0)
	num += d
	while num <= h * w:
		(x_new, y_new) = index[num - 1]
		data[i - 1].append(abs(x - x_new) + abs(y - y_new) + data[i - 1][-1])
		(x, y) = (x_new, y_new)
		num += d
q = int(input())
for i in range(q):
	(l, r) = list(map(int, input().split()))
	index_data = l % d - 1
	r = (r - 1) // d
	l = (l - 1) // d
	print(data[index_data][r] - data[index_data][l])


(H, W, D) = map(int, input().split())
A = list((list(map(int, input().split())) for i in range(H)))
B = [[0, 0] for i in range(H * W)]
for i in range(H):
	for j in range(W):
		B[A[i][j] - 1] = [i, j]
MP = [0] * (H * W)
for i in range(D):
	(x, y) = B[i]
	for j in range(i + D, H * W, D):
		MP[j] = MP[j - D] + abs(x - B[j][0]) + abs(y - B[j][1])
		(x, y) = B[j]
for i in range(int(input())):
	(l, r) = map(int, input().split())
	print(MP[r - 1] - MP[l - 1])


(h, w, d) = map(int, input().split())
A = []
for i in range(h):
	A.append(list(map(int, input().split())))
q = int(input())
I = [0] * (w * h + 1)
for i in range(h):
	for j in range(w):
		I[A[i][j]] = (i, j)
D = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
	D[i] = D[i - d] + abs(I[i][0] - I[i - d][0]) + abs(I[i][1] - I[i - d][1])
s = []
g = []
for i in range(q):
	(s, g) = map(int, input().split())
	print(D[g] - D[s])


(h, w, d) = map(int, input().split())
a = [0] * h
for i in range(h):
	a[i] = list(map(int, input().split()))
num = [[] for i in range(w * h + 1)]
for i in range(h):
	for j in range(w):
		num[a[i][j]].append([i, j])
s = [0] * (h * w + 1)
for i in range(1, h * w - d + 1):
	s[d + i] = s[i] + abs(num[d + i][0][0] - num[i][0][0]) + abs(num[d + i][0][1] - num[i][0][1])
q = int(input())
for i in range(q):
	(L, R) = map(int, input().split())
	print(s[R] - s[L])


(H, W, D) = map(int, input().split())
x = [0] * (H * W + 1)
for i in range(H):
	a = list(map(int, input().split()))
	for j in range(W):
		x[a[j]] = [i, j]
d = [0] * (H * W + 1)
for i in range(1, H * W + 1):
	if i > D:
		d[i] = d[i - D] + abs(x[i][0] - x[i - D][0]) + abs(x[i][1] - x[i - D][1])
Q = int(input())
for i in range(Q):
	(l, r) = map(int, input().split())
	print(d[r] - d[l])


(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 + 1)]
for r in range(h):
	for c in range(w):
		place[a[r][c]] = (r, c)
dp = [0] * (w * h + 1)
for r in range(1, w * h + 1):
	if r - d < 1:
		continue
	(r1, c1) = place[r - d]
	(r2, c2) = place[r]
	dp[r] = dp[r - d] + abs(r1 - r2) + abs(c1 - c2)
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(dp[r] - dp[l])


def main():
	(h, w, d) = list(map(int, input().split()))
	a = [None] * (h * w + 1)
	for i in range(1, h + 1):
		l = list(map(int, input().split()))
		for (j, k) in enumerate(l, 1):
			a[k] = (i, j)
	c = [0] * (h * w + 1)
	for i in range(d + 1, h * w + 1):
		(xb, yb) = a[i - d]
		(xn, yn) = a[i]
		c[i] = c[i - d] + abs(xn - xb) + abs(yn - yb)
	q = int(input())
	res = []
	for _ in range(q):
		(l, r) = list(map(int, input().split()))
		res.append(c[r] - c[l])
	ans = '\n'.join(map(str, res))
	print(ans)

def __starting_point():
	main()
__starting_point()


(h, w, d) = map(int, input().split())
loc = [[] for _ in range(w * h + 1)]
cost = [0] * (w * h + 1)
for i in range(h):
	l = list(map(int, input().split()))
	for j in range(w):
		loc[l[j]] = [i, j]
for t in range(w * h + 1, 0, -1):
	if t + d < w * h + 1:
		(ti, tj) = loc[t + d]
		(fi, fj) = loc[t]
		tempcost = abs(fi - ti) + abs(fj - tj)
		cost[t] = cost[t + d] + tempcost
q = int(input())
for i in range(q):
	(l, r) = map(int, input().split())
	print(cost[l] - cost[r])


(h, w, d) = tuple(map(int, input().split()))
a = [[int(t) for t in input().split()] for _ in [0] * h]
pos = [0] * (h * w)
for i in range(h):
	for j in range(w):
		pos[a[i][j] - 1] = (i, j)
cusum = [0] * d
for i in range(h * w - d):
	(x, y) = pos[i]
	(z, w) = pos[i + d]
	cost = abs(x - z) + abs(y - w)
	cusum.append(cusum[-d] + cost)
q = int(input())
for i in range(q):
	(l, r) = tuple(map(int, input().split()))
	(l, r) = (l - 1, r - 1)
	print(cusum[r] - cusum[l])


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Am = [None] * (H * W + 1)
for h in range(H):
	for w in range(W):
		Am[A[h][w]] = (h, w)
C = [0] * (H * W + 1)
for i in range(D + 1, H * W + 1):
	(h, w) = Am[i - D]
	(ch, cw) = Am[i]
	C[i] = C[i - D] + abs(ch - h) + abs(cw - w)
Q = int(input())
for _ in range(Q):
	(L, R) = map(int, input().split())
	print(C[R] - C[L])


(H, W, D) = map(int, input().split())
xy = {}
for i in range(H):
	A = list(map(int, input().split()))
	for j in range(W):
		xy[A[j]] = (i + 1, j + 1)
d = [0] * (H * W + 1)
for i in range(D + 1, H * W + 1):
	(x1, y1) = xy[i]
	(x2, y2) = xy[i - D]
	d[i] = d[i - D] + abs(x1 - x2) + abs(y1 - y2)
Q = int(input())
for _ in range(Q):
	(L, R) = map(int, input().split())
	ans = d[R] - d[L]
	print(ans)


def sol():
	(h, w, d) = map(int, input().split())
	a = [[int(i) for i in input().split()] for i in range(h)]
	t = {}
	for i in range(h):
		for j in range(w):
			t[a[i][j]] = (i, j)
	ans = [0] * (h * w + 1)
	for i in range(h * w, d, -1):
		(o, p) = t[i]
		ans[i - d] = ans[i] + abs(o - t[i - d][0]) + abs(p - t[i - d][1])
	q = int(input())
	for i in range(q):
		(l, r) = map(int, input().split())
		print(ans[l] - ans[r])
sol()


import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

def I():
	return int(input())

def F():
	return float(input())

def SS():
	return input()

def LI():
	return [int(x) for x in input().split()]

def LI_():
	return [int(x) - 1 for x in input().split()]

def LF():
	return [float(x) for x in input().split()]

def LSS():
	return input().split()

def resolve():
	(H, W, D) = LI()
	A = [LI_() for _ in range(H)]
	Q = I()
	c = [[] for _ in range(H * W)]
	for (i, j) in itertools.product(list(range(H)), list(range(W))):
		c[A[i][j]] = [i, j]
	c_cum = [0] * (H * W)
	for i in range(H * W - D):
		c_cum[i + D] = abs(c[i + D][0] - c[i][0]) + abs(c[i + D][1] - c[i][1]) + c_cum[i]
	for _ in range(Q):
		(L, R) = LI_()
		ans = c_cum[R] - c_cum[L]
		print(ans)

def __starting_point():
	resolve()
__starting_point()


(H, W, D) = map(int, input().split())
A = [()] * (H * W + 1)
for i in range(H):
	for (j, a) in enumerate(map(int, input().split())):
		A[a] = (i, j)
Q = int(input())
LR = [tuple(map(int, input().split())) for _ in range(Q)]

def distance(a, b):
	return abs(a[0] - b[0]) + abs(a[1] - b[1])
dist = [0] * (H * W + 1)
for o in range(1, D + 1):
	for i in range(o + D, H * W + 1, D):
		dist[i] = dist[i - D] + distance(A[i], A[i - D])
for (L, R) in LR:
	print(dist[R] - dist[L])


(h, w, d) = map(int, input().split())
field = [[]] * (h * w)
for i in range(h):
	x = list(map(int, input().split()))
	for j in range(w):
		field[x[j] - 1] = [i, j]
dis = [10 ** 20] * (h * w)
for i in range(d):
	dis[i] = 0
for i in range(h * w):
	if i >= d:
		dis[i] = dis[i - d] + abs(field[i][0] - field[i - d][0]) + abs(field[i][1] - field[i - d][1])
q = int(input())
for i in range(q):
	(l, r) = map(int, input().split())
	print(dis[r - 1] - dis[l - 1])


def dist(d1, d2):
	return abs(d1[0] - d2[0]) + abs(d1[1] - d2[1])
(h, w, d) = map(int, input().split())
table = {}
for i in range(h):
	a = list(map(int, input().split()))
	for j in range(w):
		table[a[j]] = (j + 1, i + 1)
cum = [0] * (h * w + 1)
for i in range(h * w + 1):
	if i > d:
		cum[i] = cum[i - d] + dist(table[i], table[i - d])
q = int(input())
for i in range(q):
	(l, r) = map(int, input().split())
	print(cum[r] - cum[l])


(H, W, D) = map(int, input().split())
px = [0] * (H * W + 1)
py = [0] * (H * W + 1)
d = [0] * (H * W + 1)
for i in range(H):
	A = list(map(int, input().split()))
	for (j, a) in enumerate(A):
		px[a] = i
		py[a] = j
for i in range(D + 1, H * W + 1):
	d[i] = d[i - D] + abs(px[i] - px[i - D]) + abs(py[i] - py[i - D])
for i in range(int(input())):
	(L, R) = map(int, input().split())
	print(d[R] - d[L])


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list('abcdefghijklmnopqrstuvwxyz')
ALF = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
INF = float('inf')
(H, W, D) = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(H)]
table = [[-1, -1] for _ in range(H * W + 1)]
for i in range(H):
	for j in range(W):
		a = A[i][j]
		if a > D:
			table[a - D][0] = i
			table[a - D][1] = j
magic = [0] * (H * W + 1)
for i in range(H):
	for j in range(W):
		a = A[i][j]
		if a <= H * W - D:
			magic[a] = abs(i - table[a][0]) + abs(j - table[a][1])
for i in range(D + 1, H * W + 1):
	magic[i] += magic[i - D]
Q = int(input())
ans = 0
for i in range(Q):
	(L, R) = list(map(int, input().split()))
	if L == R:
		print(0)
	elif L <= D:
		print(magic[R - D])
	else:
		print(magic[R - D] - magic[L - D])


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]
data = {A[i][j]: j + i * W for i in range(H) for j in range(W)}
memo = [0] * (H * W + 1)
for i in range(1 + D, H * W + 1):
	(a, b) = (data[i], data[i - D])
	memo[i] = memo[i - D] + abs(a % W - b % W) + abs(a // W - b // W)
for (l, r) in LR:
	if l == r:
		print(0)
		continue
	print(memo[r] - memo[l])


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
dic = {}
for i in range(H):
	for j in range(W):
		dic[A[i][j]] = (i, j)
dist = [0] * (H * W + 10)
for i in range(D + 1, H * W + 1):
	xd = abs(dic[i][0] - dic[i - D][0])
	yd = abs(dic[i][1] - dic[i - D][1])
	dist[i] = dist[i - D] + xd + yd
Q = int(input())
for i in range(Q):
	(L, R) = map(int, input().split())
	print(dist[R] - dist[L])


import sys
readline = sys.stdin.buffer.readline
(H, W, D) = map(int, readline().split())
px = [0] * (H * W + 1)
py = [0] * (H * W + 1)
d = [0] * (H * W + 1)
for y in range(H):
	line = list(map(int, readline().split()))
	for (x, A) in enumerate(line):
		px[A] = x
		py[A] = y
for i in range(D + 1, H * W + 1):
	d[i] = d[i - D] + abs(px[i] - px[i - D]) + abs(py[i] - py[i - D])
Q = int(input())
for _ in range(Q):
	(L, R) = map(int, input().split())
	print(d[R] - d[L])


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
B = [list(map(int, input().split())) for _ in range(Q)]
(L, R) = zip(*B)
C = [[] for i in range(H * W)]
for i in range(H):
	for j in range(W):
		a = A[i][j]
		C[a - 1] = (j + 1, i + 1)
X = [0] * (H * W + 1)
for i in range(D):
	x = H * W - D - i
	count = 0
	while x > 0:
		count += abs(C[x - 1][0] - C[x + D - 1][0]) + abs(C[x - 1][1] - C[x + D - 1][1])
		X[x] += count
		x -= D
for i in range(Q):
	print(X[L[i]] - X[R[i]])


(h, w, d) = map(int, input().split())
zahyo = [0] * (h * w + 1)
for i in range(h):
	a = list(map(int, input().split()))
	for j in range(w):
		zahyo[a[j]] = (i + 1, j + 1)
D = [0] * 100000
for i in range(d + 1, h * w + 1):
	D[i] = D[i - d] + abs(zahyo[i][1] - zahyo[i - d][1]) + abs(zahyo[i][0] - zahyo[i - d][0])
q = int(input())
for i in range(q):
	(L, R) = map(int, input().split())
	print(D[R] - D[L])


import itertools
(h, w, d) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
p = [0] * (h * w)
for (i, j) in itertools.product(range(h), range(w)):
	p[a[i][j] - 1] = (i, j)
s = [0] * d
for i in range(h * w - d):
	s.append(s[-d] + abs(p[i][0] - p[i + d][0]) + abs(p[i][1] - p[i + d][1]))
q = int(input())
for i in range(q):
	(l, r) = map(int, input().split())
	l -= 1
	r -= 1
	print(s[r] - s[l])


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
lst = [[] for _ in range(H * W)]
for i in range(H):
	for j in range(W):
		lst[A[i][j] - 1] = [j, i]
tr = [[0] for _ in range(D)]
for i in range(D):
	for j in range(i + D, W * H, D):
		dlt = abs(lst[j][0] - lst[j - D][0]) + abs(lst[j][1] - lst[j - D][1])
		tr[i].append(tr[i][-1] + dlt)
Q = int(input())
for i in range(Q):
	(l, r) = map(int, input().split())
	idx = (l - 1) % D
	if (l - 1) // D == 0:
		st = 0
	else:
		st = (l - 1) // D
	ed = (r - 1) // D
	print(tr[idx][ed] - tr[idx][st])


from collections import defaultdict
import itertools
d = defaultdict(int)
x = 'MARCH'
for i in range(5):
	d[x[i]] = i + 1
x = [0] * 5

def sub(a, b):
	return abs(a[0] - b[0]) + abs(a[1] - b[1])
(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
N = H * W
P = [0] * N
for h in range(H):
	for w in range(W):
		P[A[h][w] - 1] = (h, w)
X = []
for d in range(D):
	_ = [0] + [sub(P[i % N], P[i - D]) for i in range(d + D, N + D, D)]
	cumsum = list(itertools.accumulate(_))
	X.append(cumsum)
Q = int(input())
for q in range(Q):
	(l, r) = map(int, input().split())
	(l, r) = (l - 1, r - 1)
	g = l % D
	if l > r:
		r += N
		ans = X[g][-1] - X[g][l // D]
		ans += X[g][r // D] - X[g][0]
	else:
		ans = X[g][r // D] - X[g][l // D]
	print(ans)


(H, W, D) = list(map(int, input().split()))
X = [(0, 0) for i in range(H * W + 1)]
for i in range(1, H + 1):
	A = list(map(int, input().split()))
	for (idx, a) in enumerate(A):
		X[a] = (i, idx + 1)
Q = int(input())
L = []
R = []
S = [0] * (H * W + 1)
for i in range(Q):
	(l, r) = list(map(int, input().split()))
	L.append(l)
	R.append(r)
for i in range(D + 1, H * W + 1):
	S[i] = S[i - D] + abs(X[i][0] - X[i - D][0]) + abs(X[i][1] - X[i - D][1])
for i in range(Q):
	print(S[R[i]] - S[L[i]])


import sys
input = sys.stdin.readline
(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
loc = [None] * (H * W + 1)
for y in range(H):
	for x in range(W):
		loc[A[y][x]] = (x, y)
power = [0] * (H * W + 1)
for n in range(D + 1, H * W + 1):
	(i, j) = loc[n - D]
	(x, y) = loc[n]
	power[n] = power[n - D] + abs(x - i) + abs(y - j)
Q = int(input())
for _ in range(Q):
	(L, R) = map(int, input().split())
	print(power[R] - power[L])


(h, w, d) = list(map(int, input().split()))
lis = [[] for i in range(h * w)]
for i in range(h):
	ai = list(map(int, input().split()))
	for j in range(w):
		lis[ai[j] - 1].append(i)
		lis[ai[j] - 1].append(j)
U = []
for i in range(d):
	Ui = [0]
	j = 1
	while i + j * d < h * w:
		Ui.append(Ui[j - 1] + abs(lis[i + j * d][0] - lis[i + (j - 1) * d][0]) + abs(lis[i + j * d][1] - lis[i + (j - 1) * d][1]))
		j += 1
	U.append(Ui)
q = int(input())
for i in range(q):
	(li, ri) = [int(x) - 1 for x in input().split()]
	modi = li % d
	print(U[modi][(ri - modi) // d] - U[modi][(li - modi) // d])


def dist(x, y):
	return abs(x[0] - y[0]) + abs(x[1] - y[1])
(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
G = {}
for i in range(H):
	for j in range(W):
		G[A[i][j]] = (i, j)
C = {}
for j in range(1, D + 1):
	k = 1
	C[j] = 0
	while j + k * D <= H * W:
		C[j + k * D] = C[j + (k - 1) * D] + dist(G[j + (k - 1) * D], G[j + k * D])
		k += 1
Q = int(input())
for _ in range(Q):
	(L, R) = map(int, input().split())
	print(C[R] - C[L])


from sys import stdin
nii = lambda : map(int, stdin.readline().split())
lnii = lambda : list(map(int, stdin.readline().split()))
(h, w, d) = nii()
a_dict = {}
for i in range(h):
	a = lnii()
	for j in range(w):
		a_dict[a[j]] = (i, j)
b_dict = {}
for i in range(1, d + 1):
	num = i
	(cy, cx) = a_dict[num]
	b_dict[num] = 0
	while num + d <= h * w:
		num += d
		(ny, nx) = a_dict[num]
		b_dict[num] = b_dict[num - d] + abs(cy - ny) + abs(cx - nx)
		cy = ny
		cx = nx
q = int(input())
for i in range(q):
	(l, r) = nii()
	ans = b_dict[r] - b_dict[l]
	print(ans)


(H, W, D) = map(int, input().split())
G = [[]] * (H * W)
J = [0] * (H * W)
for i in range(H):
	for (j, a) in enumerate(list(map(int, input().split()))):
		G[a - 1] = [i, j]
for i in range(H * W):
	if i - D >= 0:
		J[i] = J[i - D] + abs(G[i][0] - G[i - D][0]) + abs(G[i][1] - G[i - D][1])
for i in range(int(input())):
	(l, r) = map(int, input().split())
	print(J[r - 1] - J[l - 1])


(H, W, D) = [int(i) for i in input().split()]
B = [(-1, -1) for _ in range(H * W)]
for h in range(H):
	A = [int(i) - 1 for i in input().split()]
	for w in range(W):
		B[A[w]] = (h, w)
C = [0] * (H * W)
for i in range(D, H * W):
	(h, w) = B[i - D]
	(nh, nw) = B[i]
	C[i] = C[i - D] + abs(nh - h) + abs(nw - w)
Q = int(input())
for (l, r) in [[int(i) - 1 for i in input().split()] for _ in range(Q)]:
	print(C[r] - C[l])


3
import numpy
from collections import defaultdict

def main():
	(h, w, d) = list(map(int, input().split()))
	mat_a = numpy.array([list(map(int, input().split())) for _ in range(h)])
	q = int(input())
	x_to_pos = dict()
	for i in range(h):
		for j in range(w):
			x_to_pos[mat_a[i, j]] = (i, j)

	def calc_score(p1, p2):
		return sum([abs(x - y) for (x, y) in zip(p1, p2)])
	visited = numpy.zeros((h, w))
	costs = defaultdict(dict)
	for c in range(1, d + 1):
		cost = 0
		costs[c % d][c] = 0
		while True:
			cp = x_to_pos[c]
			c += d
			if c > h * w:
				break
			np = x_to_pos[c]
			cost += calc_score(cp, np)
			costs[c % d][c] = cost
	for _ in range(q):
		(l, r) = list(map(int, input().split()))
		print(abs(costs[l % d][l] - costs[l % d][r]))

def __starting_point():
	main()
__starting_point()


(H, W, D) = map(int, input().split())
A = [[int(i) for i in input().split()] for i in range(H)]
L = [[] for i in range(H * W + 1)]
for i in range(H):
	for j in range(W):
		L[A[i][j]] = [i + 1, j + 1]
d = [0] * (H * W + 1)
for i in range(D + 1, H * W + 1):
	d[i] = d[i - D] + abs(L[i][0] - L[i - D][0]) + abs(L[i][1] - L[i - D][1])
Q = int(input())
for i in range(Q):
	(l, r) = map(int, input().split())
	print(d[r] - d[l])


(h, w, d) = list(map(int, input().split()))
a = [tuple(map(int, input().split())) for _ in range(h)]
inf = 1 << 30
pos = [(0, 0)] * (h * w + 1)
dist = [inf] * (h * w + 1)
for i in range(h):
	for j in range(w):
		pos[a[i][j]] = (i, j)
for i in range(1, h * w):
	if dist[i] == inf:
		dist[i] = 0
		j = i + d
		while j <= h * w:
			dist[j] = dist[j - d] + abs(pos[j][0] - pos[j - d][0]) + abs(pos[j][1] - pos[j - d][1])
			j += d
q = int(input())
for i in range(q):
	(l, r) = list(map(int, input().split()))
	print(dist[r] - dist[l])


(H, W, D) = map(int, input().split())
(X, Y, ans) = ([-1] * H * W, [-1] * H * W, [0] * H * W)
for h in range(H):
	A = list(map(int, input().split()))
	for w in range(W):
		(X[A[w] - 1], Y[A[w] - 1]) = (h, w)
for d in range(D):
	while d + D < H * W:
		ans[d + D] = ans[d] + abs(X[d] - X[d + D]) + abs(Y[d] - Y[d + D])
		d += D
Q = int(input())
for _ in range(Q):
	(L, R) = map(int, input().split())
	print(ans[R - 1] - ans[L - 1])


(H, W, D) = map(int, input().split())
pos = [0] * (H * W)
for j in range(H):
	A = list(map(int, input().split()))
	for i in range(W):
		pos[A[i] - 1] = (i, j)
memo = [0] * (H * W)
for x in range(H * W):
	if x < D:
		continue
	(i, j) = (pos[x - D][0], pos[x - D][1])
	(u, v) = (pos[x][0], pos[x][1])
	memo[x] = memo[x - D] + abs(i - u) + abs(j - v)
Q = int(input())
for _ in range(Q):
	(L, R) = map(int, input().split())
	print(memo[R - 1] - memo[L - 1])


(h, w, d) = list(map(int, input().split()))
n = h * w
paths = [[] for _ in range(d)]
for i in range(n):
	paths[i % d].append(i)

class P:

	def __init__(self, x, y):
		(self.x, self.y) = (x, y)

	def __sub__(self, p):
		return P(self.x - p.x, self.y - p.y)

	def _abs(self):
		return P(abs(self.x), abs(self.y))

	def _sum(self):
		return self.x + self.y

	def to(self, p):
		return (self - p)._abs()._sum()
coodinates = [None] * n
for i in range(h):
	for (j, a) in enumerate([int(x) - 1 for x in input().split()]):
		coodinates[a] = P(i, j)
costs = [[0] for _ in range(d)]
for i in range(d):
	for (x, y) in zip(paths[i], paths[i][1:]):
		(p, q) = (coodinates[x], coodinates[y])
		costs[i].append(costs[i][-1] + p.to(q))
q = int(input())
for _ in range(q):
	(L, R) = [int(x) - 1 for x in input().split()]
	print(costs[L % d][R // d] - costs[L % d][L // d])


(h, w, d) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]
b = [0] * (h * w + 1)
for i in range(h):
	for j in range(w):
		b[a[i][j]] = (i, j)
ans = [0] * (h * w + 1)
for i in range(d + 1, h * w + 1):
	ans[i] = ans[i - d] + abs(b[i][0] - b[i - d][0]) + abs(b[i][1] - b[i - d][1])
for i in range(q):
	(x, y) = (lr[i][0], lr[i][1])
	print(ans[y] - ans[x])


(H, W, D) = map(int, input().split())
dic = {}
memo = [0] * (H * W + 1)
for i in range(H):
	s = input().split()
	for j in range(W):
		dic[int(s[j])] = (i, j)
for i in range(1, H * W + 1):
	if i - D >= 1:
		memo[i] = memo[i - D] + abs(dic[i][0] - dic[i - D][0]) + abs(dic[i][1] - dic[i - D][1])
Q = int(input())
for _ in range(Q):
	(l, r) = map(int, input().split())
	print(memo[r] - memo[l])


import sys
readline = sys.stdin.readline
(H, W, D) = list(map(int, readline().split()))
route = [0] * (H * W + 1)
for i in range(H):
	line = list(map(int, readline().split()))
	for j in range(len(line)):
		route[line[j]] = (i, j)
dist = [0] * (H * W + 1)
for i in range(D + 1, len(route)):
	(gy, gx) = route[i]
	(sy, sx) = route[i - D]
	dist[i] = abs(gy - sy) + abs(gx - sx)
	dist[i] = dist[i] + dist[i - D]
Q = int(readline())
for i in range(Q):
	(l, r) = list(map(int, readline().split()))
	print(dist[r] - dist[l])


(h, w, d) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
num = [[] for i in range(h * w + 1)]
num[0] = [0, 0]
for i in range(h):
	for j in range(w):
		num[a[i][j]].extend([i, j])
cumsum = [0] * (h * w + 1)
for i in range(d, h * w + 1):
	(x1, y1) = num[i]
	(x2, y2) = num[i - d]
	cumsum[i] += cumsum[i - d] + abs(x1 - x2) + abs(y1 - y2)
Q = int(input())
for _ in range(Q):
	(x, y) = map(int, input().split())
	print(cumsum[y] - cumsum[x])


(h, w, d) = map(int, input().split())
l = []
for i in range(h):
	l.append(list(map(int, input().split())))
px = [0] * (h * w)
py = [0] * (h * w)
ans = [0] * (h * w)
for i in range(h):
	for j in range(w):
		px[l[i][j] - 1] = j
		py[l[i][j] - 1] = i
for i in range(d, h * w):
	ans[i] = ans[i - d] + abs(px[i] - px[i - d]) + abs(py[i] - py[i - d])
q = int(input())
for i in range(q):
	(a, b) = map(int, input().split())
	print(ans[b - 1] - ans[a - 1])


(h, w, d) = map(int, input().split())
m = [list(map(int, input().split())) for i in range(h)]
b = [0] * (h * w)
for i in range(h):
	for j in range(w):
		b[m[i][j] - 1] = [i, j]
dp = [0] * (h * w)
for i in range(d, h * w):
	dp[i] = dp[i - d] + abs(b[i][0] - b[i - d][0]) + abs(b[i][1] - b[i - d][1])
n = int(input())
for i in range(n):
	(x, y) = map(int, input().split())
	print(dp[y - 1] - dp[x - 1])


(h, w, d) = map(int, input().split())
amd = {}
for i in range(h):
	al = map(int, input().split())
	for (j, a) in enumerate(al):
		amd[a] = (j + 1, i + 1)
dsum = [0 for _ in range(d + 1)]
for i in range(d + 1, h * w + 1):
	dsum.append(dsum[-d] + abs(amd[i][0] - amd[i - d][0]) + abs(amd[i][1] - amd[i - d][1]))
q = int(input())
for _ in range(q):
	ans = 0
	(l, r) = map(int, input().split())
	print(dsum[r] - dsum[l])


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
(L, R) = zip(*(map(int, input().split()) for _ in range(Q)))
p = {A[i][j]: (i, j) for i in range(H) for j in range(W)}
dp = [0 for _ in range(H * W + 1)]
for x in range(D + 1, H * W + 1):
	y = x - D
	dp[x] = dp[y] + abs(p[x][0] - p[y][0]) + abs(p[x][1] - p[y][1])
ans = '\n'.join((str(dp[r] - dp[l]) for (l, r) in zip(L, R)))
print(ans)


(H, W, D) = map(int, input().split())
posi = [[]] * (H * W)
for _ in range(H):
	a = list(map(int, input().split()))
	for (i, j) in enumerate(a):
		posi[j - 1] = [_ + 1, i + 1]
Q = int(input())
acdist = [0] * (H * W)
for _ in range(0, H * W - D):
	acdist[_ + D] += acdist[_] + abs(posi[_ + D][0] - posi[_][0]) + abs(posi[_ + D][1] - posi[_][1])
for i in range(Q):
	(l, r) = map(int, input().split())
	print(acdist[r - 1] - acdist[l - 1])


(H, W, D) = [int(it) for it in input().split()]
li = [[int(it) - 1 for it in input().split()] for i in range(H)]
pos = [0] * (H * W)
for h in range(H):
	for w in range(W):
		pos[li[h][w]] = (h, w)
di = [0] * (H * W)
for i in range(H * W):
	if D <= i:
		(sx, sy) = pos[i - D]
		(gx, gy) = pos[i]
		di[i] = di[i - D] + abs(sx - gx) + abs(sy - gy)
Q = int(input())
for i in range(Q):
	(l, q) = [int(it) - 1 for it in input().split()]
	print(di[q] - di[l])


import sys
readline = sys.stdin.readline
read = sys.stdin.read
(h, w, d) = map(int, readline().split())
a = [list(map(int, readline().split())) for _ in range(h)]
(q, *lr) = map(int, read().split())
ca = dict()
for (i, l) in enumerate(a):
	for (j, e) in enumerate(l):
		ca[e] = (i + 1, j + 1)
mp = [[0] * (h * w // d + 1) for _ in range(d)]
for (i, mpl) in enumerate(mp):
	for (j, _) in enumerate(mpl[:-1]):
		if 0 < i + d * j <= h * w - d:
			mpl[j + 1] = mpl[j] + abs(ca[i + d * j][0] - ca[i + d * (j + 1)][0]) + abs(ca[i + d * j][1] - ca[i + d * (j + 1)][1])
for (l, r) in zip(*[iter(lr)] * 2):
	print(mp[l % d][r // d] - mp[l % d][l // d])


(H, W, D) = map(int, input().split())
a = [[0, 0] for i in range(H * W)]
for i in range(H):
	A = [int(j) for j in input().split()]
	for j in range(W):
		a[A[j] - 1][0] = i
		a[A[j] - 1][1] = j
Q = int(input())
b = [0] * H * W
i = D
while i < H * W:
	b[i] += abs(a[i - D][0] - a[i][0])
	b[i] += abs(a[i - D][1] - a[i][1])
	b[i] += b[i - D]
	i += 1
for i in range(Q):
	(L, R) = map(int, input().split())
	print(b[R - 1] - b[L - 1])


(H, W, D) = map(int, input().split())
num = [[] for i in range(H * W + 1)]
for i in range(H):
	A = list(map(int, input().split()))
	for j in range(W):
		num[A[j]] = [i + 1, j + 1]
cost = [0 for i in range(D)]
for i in range(H * W - D):
	cost.append(cost[i] + abs(num[H * W - i][0] - num[H * W - i - D][0]) + abs(num[H * W - i][1] - num[H * W - i - D][1]))
cost.append(None)
cost.reverse()
Q = int(input())
for i in range(Q):
	(L, R) = map(int, input().split())
	print(cost[L] - cost[R])


(h, w, d) = map(int, input().split())
tab = [[0, 0]] * (w * h)
for hi in range(h):
	t = list(map(int, input().split()))
	for wi in range(w):
		tab[t[wi] - 1] = [hi, wi]
cost = [0] * (w * h)
for i in range(d, w * h):
	a = tab[i - d]
	b = tab[i]
	cost[i] = abs(a[0] - b[0]) + abs(a[1] - b[1]) + cost[i - d]
q = int(input())
for i in range(q):
	(l, r) = map(int, input().split())
	print(cost[r - 1] - cost[l - 1])


(H, W, D) = map(int, input().split())
A = []
for i in range(H):
	A.append(list(map(int, input().split())))
num = [() for _ in range(H * W + 1)]
for i in range(H):
	for j in range(W):
		num[A[i][j]] = (i, j)
wa = [0] * (H * W + 1)
for i in range(D + 1, H * W + 1):
	wa[i] = wa[i - D] + abs(num[i][0] - num[i - D][0]) + abs(num[i][1] - num[i - D][1])
Q = int(input())
for i in range(Q):
	(l, r) = map(int, input().split())
	print(wa[r] - wa[l])


(H, W, D) = map(int, input().split())
Aindex = [0] * (H * W)
for h in range(H):
	w = 0
	for A in input().split():
		Aindex[int(A) - 1] = (h, w)
		w += 1
import numpy as np
(v, h) = (int(np.ceil(H * W / D)), D)
Mp = np.zeros((v, h))
mp = lambda X, Y: abs(X[0] - Y[0]) + abs(X[1] - Y[1])
for x in range(D, H * W):
	(i, j) = divmod(x, D)
	Mp[i, j] = mp(Aindex[x], Aindex[x - D])
Mp = Mp.cumsum(axis=0)
Q = int(input())
Query = [(int(x) for x in input().split()) for _ in range(Q)]
for (l, r) in Query:
	ans = Mp[divmod(r - 1, D)] - Mp[divmod(l - 1, D)]
	print(int(ans))


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
X = [list(map(int, input().split())) for _ in range(Q)]
ctr = {}
for i in range(H):
	for j in range(W):
		ctr[A[i][j]] = (i, j)
memo = [0] * (H * W + 1)
for n in range(D + 1, H * W + 1):
	(i, j) = ctr[n - D]
	(x, y) = ctr[n]
	memo[n] = abs(x - i) + abs(y - j) + memo[n - D]
for (l, r) in X:
	print(memo[r] - memo[l])


(h, w, d) = map(int, input().split())
l = [[0, 0]] + [[] for _ in range(h * w)]
for i in range(h):
	for (j, a) in enumerate(map(int, input().split())):
		l[a] = [i, j]
for a in l[:d]:
	a.append(0)
for (i, j) in zip(l[d:], l):
	(a, b) = i
	(x, y, v) = j
	i.append(abs(x - a) + abs(y - b) + v)
l = [c for (a, b, c) in l]
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(l[b] - l[a])


from sys import stdin
nii = lambda : map(int, stdin.readline().split())
lnii = lambda : list(map(int, stdin.readline().split()))
(h, w, d) = nii()
a_dict = {}
for i in range(h):
	a = lnii()
	for j in range(w):
		a_dict[a[j]] = (i, j)
b_dict = {}
for i in range(1, h * w + 1):
	if i - d <= 0:
		b_dict[i] = 0
	else:
		(oy, ox) = a_dict[i - d]
		(ny, nx) = a_dict[i]
		b_dict[i] = b_dict[i - d] + abs(ny - oy) + abs(nx - ox)
q = int(input())
for i in range(q):
	(l, r) = nii()
	ans = b_dict[r] - b_dict[l]
	print(ans)


(h, w, d) = map(int, input().split())
p = [0] * (h * w)
for i in range(h):
	a = list(map(int, input().split()))
	for j in range(w):
		p[a[j] - 1] = (i, j)
x = [0] * d
calc = lambda x1, y1, x2, y2: abs(x1 - x2) + abs(y1 - y2)
for i in range(d, h * w):
	x.append(x[i - d] + calc(p[i][0], p[i][1], p[i - d][0], p[i - d][1]))
for i in range(int(input())):
	(l, r) = map(int, input().split())
	print(x[r - 1] - x[l - 1])


import sys
input = sys.stdin.readline
(H, W, D) = map(int, input().split())
A = []
for h in range(H):
	A = A + list(map(int, input().split()))
for i in range(H * W):
	A[i] = (A[i], i % W, i // W)
A.sort()
Dist = [0] * (H * W)
for i in range(H * W):
	if i >= D:
		Dist[i] = Dist[i - D] + abs(A[i][1] - A[i - D][1]) + abs(A[i][2] - A[i - D][2])
Q = int(input())
for q in range(Q):
	(L, R) = map(int, input().split())
	ret = Dist[R - 1] - Dist[L - 1]
	print(ret)


(H, W, D) = map(int, input().split())
m = [None] * (H * W + 1)
for i in range(H):
	l = map(int, input().split())
	for (j, a) in enumerate(l):
		m[a] = (i, j)
Q = int(input())
LR = []
for _ in range(Q):
	(l, r) = map(int, input().split())
	LR.append((l, r))
S = [0] * (H * W + 1)
for k in range(D + 1, H * W + 1):
	(x, y) = m[k]
	(i, j) = m[k - D]
	S[k] = S[k - D] + abs(x - i) + abs(y - j)
for (l, r) in LR:
	print(S[r] - S[l])


(H, W, D) = map(int, input().split())
A = [[int(e) - 1 for e in input().split()] for _ in range(H)]
Q = int(input())
query = [[int(e) - 1 for e in input().split()] for _ in range(Q)]
mp = [0] * (H * W)
x = [-1] * (H * W)
y = [-1] * (H * W)
for (i, line) in enumerate(A):
	for (j, a) in enumerate(line):
		x[a] = i
		y[a] = j
for i in range(D, H * W):
	mp[i] = mp[i - D] + abs(x[i] - x[i - D]) + abs(y[i] - y[i - D])
for (l, r) in query:
	print(mp[r] - mp[l])


(h, w, d) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
Q = int(input())
lis = [0] * (h * w)
for i in range(h):
	for j in range(w):
		lis[a[i][j] - 1] = (i, j)
cum = [0] * d
for i in range(d, h * w):
	cum.append(cum[i - d] + abs(lis[i][0] - lis[i - d][0]) + abs(lis[i][1] - lis[i - d][1]))
for i in range(Q):
	(l, r) = map(int, input().split())
	print(cum[r - 1] - cum[l - 1])


(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
As = [(0, 0, 0)]
for i in range(H):
	for j in range(W):
		As.append((A[i][j], i + 1, j + 1))
Q = int(input())
Qs = [list(map(int, input().split())) for _ in range(Q)]
As.sort()
dp = [0] * (H * W + 1)
for i in range(1, H * W + 1 - D):
	(a1, j, k) = As[i]
	(a2, x, y) = As[i + D]
	dp[i + D] = dp[i] + abs(x - j) + abs(y - k)
for (l, r) in Qs:
	print(dp[r] - dp[l])


def main():
	(H, W, D) = map(int, input().split())
	coordinate = [None] * (H * W)
	for i in range(H):
		for (j, A) in enumerate(list(map(int, input().split()))):
			coordinate[A - 1] = (i, j)
	cost = [0] * (H * W)
	dist = lambda X, Y: abs(X[0] - Y[0]) + abs(X[1] - Y[1])
	for i in range(D, H * W):
		(u, v) = divmod(i, D)
		cost[i] = cost[i - D] + dist(coordinate[i], coordinate[i - D])
	Q = int(input())
	query = [tuple(map(int, input().split())) for _ in range(Q)]
	for (l, r) in query:
		print(cost[r - 1] - cost[l - 1])
main()


(h, w, d) = map(int, input().split())
index = [(0, 0) for x in range(h * w + 1)]
for i in range(1, h + 1):
	col = list(map(int, input().split()))
	for j in range(1, w + 1):
		index[col[j - 1]] = (i, j)
memo = [0 for x in range(h * w + 1)]
l = 0
for l in range(1, h * w + 1 - d):
	memo[l + d] = memo[l] + abs(index[l + d][0] - index[l][0]) + abs(index[l + d][1] - index[l][1])
q = int(input())
for i in range(q):
	(l, r) = map(int, input().split())
	print(memo[r] - memo[l])


(h, w, d) = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]
arys = [[] for i in range(d)]
sumarys = [[0] for i in range(d)]
biarys = [[] for i in range(d)]
for i in range(h):
	for j in range(w):
		x = a[i][j] % d
		arys[x].append((a[i][j], i, j))
for i in range(d):
	arys[i].sort(key=lambda x: x[0])
	tmp = 0
	(y, pi, pj) = arys[i][0]
	biarys[i].append(y)
	for j in range(1, len(arys[i])):
		(y, ni, nj) = arys[i][j]
		biarys[i].append(y)
		tmp += abs(pi - ni) + abs(pj - nj)
		sumarys[i].append(tmp)
		(pi, pj) = (ni, nj)
from bisect import bisect_left
for (l, r) in lr:
	x = l % d
	li = bisect_left(biarys[x], l)
	ri = bisect_left(biarys[x], r)
	print(sumarys[x][ri] - sumarys[x][li])


(H, W, D) = map(int, input().split())
mass = [0] * (H * W + 1)
for y in range(1, H + 1):
	for (x, i) in enumerate(input().split()):
		mass[int(i)] = (y, x + 1)
Q = int(input())
dp = [H * W + 2] * (H * W + 1)
for i in range(1, H * W + 1):
	if i > D:
		dp[i] = dp[i - D] + abs(mass[i][0] - mass[i - D][0]) + abs(mass[i][1] - mass[i - D][1])
	else:
		dp[i] = mass[i][0] + mass[i][1]
for _ in range(Q):
	(L, R) = map(int, input().split())
	print(dp[R] - dp[L])


(h, w, d) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(h)]
dic = {}
for i in range(h):
	for j in range(w):
		dic[a[i][j]] = (i, j)
cnt = [0] * (h * w + 1)
for j in range(1, d + 1):
	for i in range(j, h * w - d + 1, d):
		(y1, x1) = dic[i + d]
		(y2, x2) = dic[i]
		cnt[i + d] = cnt[i] + abs(x2 - x1) + abs(y2 - y1)
q = int(input())
for _ in range(q):
	(l, r) = map(int, input().split())
	print(cnt[r] - cnt[l])


def inpl():
	return map(int, input().split())
(H, W, D) = inpl()
L = [(0, 0) for _ in range(H * W + 1)]
DP = [0] * (H * W + 1)
for i in range(H):
	for (j, a) in enumerate(inpl()):
		L[a] = (i + 1, j + 1)
for x in range(D, H * W + 1):
	DP[x] = DP[x - D] + abs(L[x][0] - L[x - D][0]) + abs(L[x][1] - L[x - D][1])
for _ in range(int(input())):
	(l, r) = inpl()
	print(DP[r] - DP[l])


(H, W, D) = map(int, input().split())
l = [None] * (H * W + 1)
for i in range(H):
	s = tuple(map(int, input().split()))
	for j in range(W):
		l[s[j]] = (i, j)
S = [0] * (H * W + 1)
for i in range(D + 1, H * W + 1):
	S[i] = S[i - D] + abs(l[i][0] - l[i - D][0]) + abs(l[i][1] - l[i - D][1])
Q = int(input())
for i in range(Q):
	(L, R) = map(int, input().split())
	print(S[R] - S[L])


def calc(x):
	if x < D + 1:
		mv[x] = 0
		return 0
	else:
		p = d[x][0]
		q = d[x][1]
		r = d[x - D][0]
		s = d[x - D][1]
		tmp = abs(p - r) + abs(q - s)
		ret = tmp + calc(x - D)
		mv[x] = ret
		return ret
import sys
sys.setrecursionlimit(10 ** 5)
(H, W, D) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
d = dict()
z = 0
for a in A:
	for b in a:
		p = z // W
		q = z % W
		d[b] = (p, q)
		z += 1
mv = [0] * (H * W + 1)
for i in range(D):
	calc(H * W - i)
L = [0] * Q
R = [0] * Q
for _ in range(Q):
	(L, R) = map(int, input().split())
	print(mv[R] - mv[L])


ai = lambda : list(map(int, input().split()))
(h, w, d) = ai()
ph = [0 for _ in range(h * w + 1)]
pw = [0 for _ in range(h * w + 1)]
for i in range(h):
	a = ai()
	for j in range(w):
		ph[a[j]] = i
		pw[a[j]] = j
score = [0 for _ in range(h * w + 1)]
for i in range(d + 1, h * w + 1):
	score[i] = score[i - d] + abs(ph[i] - ph[i - d]) + abs(pw[i] - pw[i - d])
q = int(input())
for _ in range(q):
	(l, r) = ai()
	print(score[r] - score[l])