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: interview

Starter code:

Solutions:
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
    
    # print(acc)
    for lr in LR:
        l, r = lr
        series = l%D if l%D != 0 else D
        # print("---")
        # print(series)
        # print(l, r)
        print((acc[series][(r-series)//D] - acc[series][(l-series)//D]))
            



if '__main__' == __name__:
    resolve()


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

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




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
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
#from decimal import *

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)

#print(power)
power_acc = []
for x in power:
	power_acc.append(list(accumulate(x)))
power_acc[0].insert(0, 0)
#print(power_acc)

Q = INT()
for _ in range(Q):
	L, R = MAP()
	print(power_acc[R%D][R//D] - power_acc[L%D][L//D])

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())
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をMod D別に計算する予定
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])
#縦軸方向に累積和を取っておき、後のクエリにO(1)で対応
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))

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

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


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)

import sys
from itertools import accumulate

input = sys.stdin.readline


def solve(H, W, D, A, Q, LR):
    position = [None] * (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 = [str(mp[r] - mp[l]) for l, r in LR]
    ans = "\n".join(ans)
    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 = solve(H, W, D, A, Q, LR)
    print(ans)


def __starting_point():
    main()

__starting_point()

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


def main():
  H,W,D=list(map(int,input().split()))
  A=[]
  for h in range(H):
    for w,a in enumerate(map(int,input().split())):
      A+=[[a,h,w]]
  A.sort(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())
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 = 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)
#print(b)
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])
#print(ans)
for i in range(q):
    x,y = lr[i][0],lr[i][1]
    print(ans[y]-ans[x])

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

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]

    # print(d)

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

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
from itertools import accumulate

input = sys.stdin.readline


def solve(H, W, D, A, Q, LR):
    position = [None] * (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]
    ans = "\n".join(map(str, ans))
    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 = solve(H, W, D, A, Q, LR)
    print(ans)


def __starting_point():
    main()

__starting_point()

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]
        #print("po:",j, 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]))


#!/usr/bin/env python3
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)

    # print(A)
    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 = 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])

# print(d)

Q = int(input())
for _ in range(Q):
    l, r = list(map(int, input().split()))
    print((d[r]-d[l]))


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

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

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


# coding: utf-8
import sys

# from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush
# from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
import math
# from itertools import product, accumulate, combinations, product
import bisect
# import numpy as np
# from copy import deepcopy
#from collections import deque
# from decimal import Decimal
# from numba import jit

INF = 1 << 50
EPS = 1e-8
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
            #print(mostL, mostR)
            for v in range(mostR - D, mostL-D, -D):
                #print(v, V[v])
                ni, nj = V[v]
                tmp += abs(ni - ci) + abs(nj - cj)
                cache[v] = tmp
                ci, cj = ni, nj
        #print(cache)
        print((cache[l] - cache[r]))


def __starting_point():
    #print(math.gcd(0, 10))
    run()

__starting_point()

import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

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


# ===CODE===

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 + d
        while num < h * w:
            xi, yi = pos[num]
            tmp = abs(xi - x) + abs(yi - y)
            cum[i].append(cum[i][-1] + tmp)
            x, y = xi, yi
            num += d

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

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

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):
#    print(k)
    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])

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())
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 = 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))
print(*result, sep='\n')


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 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 LF(): return [float(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))

  # print(to_last_distance)

  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()
# print(main())


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


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)

# 1,2,3 ... の頂点番号を格納した配列を作る
# D個おきに距離を格納する

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


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

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

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

# 1 -> 1+D ->
# 2 -> 2+D ->
# 3 -> 3+D -> みたいなものを事前に計算

# 辞書で管理する
# d[A[i][j]] = [i,j] みたいな感じ
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]))


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

import sys
from itertools import accumulate

input = sys.stdin.readline


def solve(H, W, D, A, Q, LR):
    position = [None] * (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 = [str(mp[r] - mp[l]) for l, r in LR]
    ans = "\n".join(ans)
    return ans


def main():
    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)]

    ans = solve(H, W, D, A, Q, LR)
    print(ans)


def __starting_point():
    main()

__starting_point()

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)))
#print(*result, sep='\n')


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


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)

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


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), dtype='int64') #MpをMod D別に計算する予定
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])
#縦軸方向に累積和を取っておき、後のクエリにO(1)で対応
Mp = Mp.cumsum(axis=0)

#クエリ処理
Q = int(input())
Query = [tuple(map(int, input().split())) for _ in range(Q)]
for l,r in Query:
    ans = Mp[divmod(r-1, D)] - Mp[divmod(l-1, D)]
    print(ans)

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


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

import sys

import numpy as np

input = sys.stdin.readline


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

import sys
from itertools import accumulate

input = sys.stdin.readline


def solve(H, W, D, A, Q, LR):
    position = [None] * (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 = [str(mp[r] - mp[l]) for l, r in LR]
    ans = "\n".join(ans)
    return ans


def main():
    H, W, D = list(map(int, input().split()))
    A = [tuple(map(int, input().split())) for _ in range(H)]
    Q = int(input())
    LR = [tuple(map(int, input().split())) for _ in range(Q)]

    ans = solve(H, W, D, A, Q, LR)
    print(ans)


def __starting_point():
    main()

__starting_point()

import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

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


# ===CODE===

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


import sys
from itertools import accumulate

input = sys.stdin.readline


def solve(H, W, D, A, Q, LR):
    position = [None] * (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 = [str(mp[r] - mp[l]) for l, r in LR]
    ans = "\n".join(ans)
    return ans


def main():
    H, W, D = list(map(int, input().split()))
    A = [tuple(map(int, input().split())) for _ in range(H)]
    Q = int(input())
    LR = [tuple(map(int, input().split())) for _ in range(Q)]

    ans = solve(H, W, D, A, Q, LR)
    print(ans)


def __starting_point():
    main()

__starting_point()

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 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

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):
		#print(dic)
		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])

#print(dic)
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=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]))


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)

# Dで分類した累積和
# S[initial % D][j], n = r + D*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)
# print(S)
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())
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]
    
#print(x)
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])

#print(d)    
Q = int(input())
for i in range(Q):
  l, r = map(int, input().split())
  print(d[r] - d[l])

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

import sys
import math
import collections
import bisect
import itertools

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

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


# ===CODE===

def main():
    h, w, d = ns()
    pos = dict()
    for i in range(h):
        a = na()
        for j, ai in enumerate(a):
            pos[ai] = (i, j)

    cum = [[0] for _ in range(d)]

    for i in range(d):
        x, y = pos[i + 1]
        num = i + 1
        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 = xi
            y = yi

    q = ni()
    for _ in range(q):
        l, r = ns()
        l -= 1
        r -= 1
        tmp = cum[l % d][r // d] - cum[l % d][l // d]
        print(tmp)


def __starting_point():
    main()

__starting_point()

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

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

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

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


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

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

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())
a = {}
for y in range(h):
    line = list(map(int, input().split()))
    for x in range(len(line)):
        a[line[x]-1] = (y,x)

# 問題の考え方
# DP的な感じで解ける
# まずGridになっているが、1次元の配列として考える 3*3(=9マスある状態) なら
#   1,2,3,4,5,6,7,8,9
# このときに数値の低い方から高い方へいくとゴールにつく(Ri-LiがDの倍数であること)が保証されるので最後の数字へ向かうときにかかるコストを考える(以下、3*3の例)
#   D=2としたときに、9はこれ以上進めないので、コスト0, 8もそれ以上進めないので コスト0, 7は9に行けるので9のコスト+7から9へ向かうコストで算出可能
#   また、5~9へのコストは1~9へのコスト引く1~5までのコストとなるので累積和的に答えを算出することが可能

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

#!/usr/bin/env python3

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)
        # index[a[j]-1] = (i, j)
# print(index)

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].append(abs(x-x_new)+abs(y-y_new)+data[i-1][-1])
        x, y = x_new, y_new
        num += d
# print(data)

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


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


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)
c = [0]*(h*w+1)
for i in range(d+1,h*w+1):
  c[i] = c[i-d] + abs(b[i][0]-b[i-d][0])+abs(b[i][1]-b[i-d][1])
for l,r in lr:
  print(c[r]-c[l])

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

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

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
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
#from decimal import *

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)

#print(power)
power_acc = []
for x in power:
	power_acc.append(list(accumulate(x)))
#print(power_acc)

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

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]




# magic is just distance by 1

# if d is 4,
# 1,5,9 or 2,6,10.. make surplus to categorize
# query comes 10^5, so O(1) or O(logN) is limit -> cumulativesum

dp = [0 for i in range(h*w+1)]
for i in range(d): # 0,1,2,...d-1
    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 = 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))))


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

3
# -*- coding:utf-8 -*-

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

import sys
from itertools import accumulate

input = sys.stdin.readline


def solve(H, W, D, A, Q, LR):
    position = [None] * (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 = [str(mp[r] - mp[l]) for l, r in LR]
    ans = "\n".join(ans)
    return ans


def main():
    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)]

    ans = solve(H, W, D, A, Q, LR)
    print(ans)


def __starting_point():
    main()

__starting_point()

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

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

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")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
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))
    else:
        if L <= D:
            print((magic[R-D]))
        else:
            print((magic[R-D]-magic[L-D]))





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)



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


# https://atcoder.jp/contests/abc089/tasks/abc089_d

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)
    #print(H*W-i,calc(H*W-i))    
#print(mv)

L=[0]*Q
R=[0]*Q
for _ in range(Q):
    L,R=map(int,input().split())
    print(mv[R]-mv[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)

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)

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