Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque

N,M,P=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]		#隣接リスト
rev_al=[ [] for i in range(N+1) ]	#reverse隣接リスト
#辺のリスト
edge=[]

for i in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	al[a].append(b)
	rev_al[b].append(a)
	edge.append((a,b,c-P))


#ゴールからBFS
q=deque()
q.append(N)
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
while q:
	fro=q.popleft()
	Visit[fro]=1
	for to in rev_al[fro]:
		if Visit[to]==0:
			q.append(to)
			
Visit1=Visit

#スタートからBFS
q=deque()
q.append(1)
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
while q:
	fro=q.popleft()
	Visit[fro]=1
	for to in al[fro]:
		if Visit[to]==0:
			q.append(to)

Visit2=Visit

#1からもNからも到達可能な頂点の集合
V=[]
for v1,v2 in zip(Visit1,Visit2):
	V.append(v1&v2)

new_N=sum(V)

fedge=[]	#必要な要素だけをフィルターした辺集合
for a,b,c in edge:
	if V[a]==1 and V[b]==1:
		fedge.append((a,b,c))


D=[ float("-inf") ]*(N+1)	#頂点１からの距離 1-indexed
D[1]=0

#ベルマンフォード
for i in range(new_N):
	for a,b,c in fedge:
		if D[a]==float("-inf"): continue
		alt=D[a]+c
		if D[b]<alt:
			D[b]=alt
			if i==new_N-1:
				print -1
				quit()

print max(0,D[N])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque

N,M,P=map(int, sys.stdin.readline().split())

al=[ [] for i in range(N+1) ]		#隣接リスト
rev_al=[ [] for i in range(N+1) ]	#reverse隣接リスト
#辺のリスト
edge=[]

for i in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	al[a].append(b)
	rev_al[b].append(a)
	edge.append((a,b,c-P))


#ゴールからBFS
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(N)
Visit[N]=1
while q:
	fro=q.popleft()
	for to in rev_al[fro]:
		if Visit[to]==0:
			Visit[to]=1
			q.append(to)
			
Visit1=Visit

#スタートからBFS
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(1)
Visit[1]=1
while q:
	fro=q.popleft()
	for to in al[fro]:
		if Visit[to]==0:
			Visit[to]=1
			q.append(to)

Visit2=Visit

#1からもNからも到達可能な頂点の集合
V=[]
for v1,v2 in zip(Visit1,Visit2):
	V.append(v1&v2)

new_N=sum(V)

fedge=[]	#必要な要素だけをフィルターした辺集合
for a,b,c in edge:
	if V[a]==1 and V[b]==1:
		fedge.append((a,b,c))


D=[ float("-inf") ]*(N+1)	#頂点１からの距離 1-indexed
D[1]=0

#ベルマンフォード
for i in range(new_N):
	for a,b,c in fedge:
		if D[a]==float("-inf"): continue
		alt=D[a]+c
		if D[b]<alt:
			D[b]=alt
			if i==new_N-1:
				print -1
				quit()

print max(0,D[N])
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
    b=input()
    d=a.count(b)
    if d==0:
        a.append(b)
print(len(a))


### FIXED CODE ###

n=int(input())
a=set()
for i in range(n):
    b=input()
    a.add(b)
print(len(a))
### BUGGY CODE ###

N = int(input())
X = list(input())


def f(cnt):
    if (cnt > 0):
        p_count = bin(cnt).count('1')
        return f(cnt % p_count) + 1
    else:
        return 0


for i, x in enumerate(X):
    if (x == '1'):
        X[i] = '0'
        num = int(''.join(X), 2)
        print(f(num))
        X[i] = '1'
    else:
        X[i] = '1'
        num = int(''.join(X), 2)
        print(f(num))
        X[i] = '0'

### FIXED CODE ###

#!/usr/bin/env python3
N = int(input())
X = input()

x_num = int(X, 2)
cnt1 = X.count('1')

p_zero = x_num % (cnt1 + 1)
p_one = (x_num % (cnt1 - 1) if cnt1 - 1 > 0 else 1)


def f(cnt):
    if (cnt > 0):
        pcount = p_count(cnt)
        return f(cnt % pcount) + 1
    else:
        return 0


def p_count(x):
    cnt = 0
    while (x > 0):
        if x % 2 != 0:
            cnt += 1
        x //= 2
    return cnt


def f1(x):
    cnt = 0
    while (x > 0):
        x %= bin(x).count('1')
        cnt += 1
    return cnt


for i, x in enumerate(list(X)):
    if (x == '1'):
        #x_num = int(''.join(X), 2)
        if cnt1 - 1 > 0:
            xxx = (p_one - pow(2, (N - (i + 1)), cnt1 - 1)) % (cnt1 - 1)
            xxx += cnt1 - 1 if xxx < 0 else 0
            print(f1(xxx) + 1)
        else:
            print(0)
    else:
        #x_num = int(''.join(X), 2)
        xxx = (p_zero + pow(2, (N - (i + 1)), cnt1 + 1)) % (cnt1 + 1)
        xxx += cnt1 + 1 if xxx < 0 else 0
        print(f1(xxx) + 1)
### BUGGY CODE ###

import sys

n, m = input().split()
i = [input() for i in range(int(m))]

n_l = [0] * int(n)
w_l = [0] * int(n)
p_l = []

a = 0
w = 0
for i_s in i:
    p, c = i_s.split()
    p = int(p) - 1
    if p not in p_l:
        p_l.append(p)

    if n_l[p] == 1:
        continue

    if c == "AC":
        n_l[p] = 1
    else:
        w_l[p] += 1

for p in p_l:
    if n_l[p] == 1:
        a += 1
        w += w_l[p]

print("{} {}".format(a, w))


### FIXED CODE ###

import sys
import numpy as np

n, m = input().split()
i = [input() for i in range(int(m))]

n_l = [False] * int(n)
w_l = [0] * int(n)

for i_s in i:
    p, c = i_s.split()
    p = int(p) - 1
    if n_l[p] == 1:
        continue

    if c == "AC":
        n_l[p] = True
    else:
        w_l[p] += 1

n_l = np.array(n_l)
w_l = np.array(w_l)
w_l = w_l[n_l]

print("{} {}".format(n_l.sum(), w_l.sum()))
### BUGGY CODE ###

N,M,K = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
a,b = [0],[0]
for i in range(N):
  a.append(a[i]+A[i])
for j in range(M):
  b.append(b[j]+B[j])
max = 0
#print(a,b,N+1)
for i in range(N+1):
  if a[i] > K:
    break
  j = 0
  while K - a[i] >= b[j]:
    if max < i + j:
      max = i + j
    if j >= M:
      break
    j = j+1

print(max)

### FIXED CODE ###

N,M,K = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
a,b = [0],[0]
for i in range(N):
  a.append(a[i]+A[i])
for j in range(M):
  b.append(b[j]+B[j])
ans = 0
#print(a,b,N+1)
j = M
for i in range(N+1):
  if a[i] > K:
    break

  while K - a[i] < b[j]:
    j = j-1
  ans = max(ans,i+j)

print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = str(input())
ls = [list(map(int, input().split()))  for i in range(q)]
for i in range(q):
    l, r = ls[i][0], ls[i][1]
    ans = s[l - 1: r].count('AC')
    print(ans)

### FIXED CODE ###

n, q = map(int, input().split())
s = str(input())
ls = [list(map(int, input().split())) for i in range(q)]
t = [0] * (n + 1)
for i in range(n):
    t[i + 1] = t[i] + (1 if s[i:i + 2] == 'AC' else 0)
for i in range(q):
    l, r = ls[i][0], ls[i][1]
    ans = t[r - 1] - t[l - 1]
    print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())

h = list(map(int,input().split()))

INF = 100100100100100
dp = [INF]*N

dp[0] = 0

for i in range(1,N):
    for k in range(1,K+1):
        if i >= k:
            dp[i] = min(dp[i], dp[i-k] + abs(h[i] - h[i-k]))
        
print(dp[N-1])

### FIXED CODE ###

N,K = map(int,input().split())

h = list(map(int,input().split()))

INF = 100100100100100
dp = [INF]*N

dp[0] = 0

for i in range(1,N):
    for k in range(1,K+1):
        if i < k:
            break
        dp[i] = min(dp[i], dp[i-k] + abs(h[i] - h[i-k]))
        
print(dp[N-1])
### BUGGY CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A_acc = [0] * (N + 1)
B_acc = [0] * (M + 1)
acc = 0
for i, a in enumerate(A):
    acc += a
    A_acc[i+1] = acc
acc = 0
for i, b in enumerate(B):
    acc += b
    B_acc[i+1] = acc
ans = 0
for i in range(N + 1):
    if A_acc[i] > K:
        break
    for j in range(M,-1,-1):
        if A_acc[i] + B_acc[j] <= K:
            ans = max(ans, i + j)
            break
print(ans)


### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
if K >= sum(A) + sum(B):
    print(M + N)
    exit()
acc = 0
ans = 0
for j, b in enumerate(B):
    acc += b
    if K >= acc:
        ans = j + 1
for i in range(N):
    acc += A[i]
    if K >= acc:
        ans = max(ans, i + j + 2)
        continue
    else:
        while (K < acc) & (j > -1):
            acc -= B[j]
            j -= 1
        if K >= acc:
            ans = max(ans, i + j + 2)
print(ans)
### BUGGY CODE ###

n = int(input())
xlist = []
for i in range(n):
    command = list(map(str,input().split()))
    if (command[0] == 'insert'):
        x = command[1]
        if (len(xlist) == 0):
            xlist.append(int(x))
        else:
            xlist = [int(x)] + xlist
        #print(xlist)
    elif (command[0] == 'delete'):
        x = command[1]
        if (int(x) in xlist) :
            xlist.remove(int(x))
        #print(xlist)
    elif (command[0] == 'deleteFirst'):
        if (len(xlist) > 0):
            del xlist[0]
        #print(xlist)
    elif (command[0] == 'deleteLast'):
        if (len(xlist) > 0):
            del xlist[-1]
        #print(xlist)
n = len(xlist)
for i in range(n):
    if (i == n-1):
        print('{}'.format(xlist[i]), end = '')
    else:
        print('{} '.format(xlist[i]), end = '')
print()


### FIXED CODE ###

from collections import deque
n = int(input())
a = deque()
for i in range(n):
    c = input()
    if c == "deleteFirst":
        a.popleft()
    elif c == "deleteLast":
        a.pop()
    else:
        c, v = c.split()
        if c == "insert":
            a.appendleft(v)
        else:
            try:
                a.remove(v)
            except:
                pass
print(" ".join(a))
### BUGGY CODE ###

N = int(input())
V = [int(i) for i in input().split()] 
C = [int(i) for i in input().split()] 

ans = []

for i in range(1<<N):
    X = 0
    Y = 0
    for j in range(N):
        if ((i >> j) & 1) == 1:
            X += V[j]
            Y += C[j]
    ans.append(X-Y)

print(max(ans))

### FIXED CODE ###

N = int(input())
V = [int(i) for i in input().split()] 
C = [int(i) for i in input().split()] 

ans = []

for i in range(1<<N):
    X = 0
    Y = 0
    for j in range(N):
        if ((i >> j) & 1) == 1:
            X += V[j]
            Y += C[j]
    ans.append(X-Y)

print(max(ans))
### BUGGY CODE ###

n,m=map(int,input().split())
if n*2>=m:
  print(m//2)
else:
  while m-n*2>=4:
    n+=1
    m-=2
  print(n)

### FIXED CODE ###

n,m=map(int,input().split())
if n*2>=m:
  print(m//2)
else:
  d=m-n*2
  print(n+d//4)
### BUGGY CODE ###

N,M =[int(i)for i in input().split()]
oya =[[]for i in range(N)]
ko =[[] for i in range(N)]
tyo =set([i for i in range(N)])
for _ in range(N+M-1):
    A,B = [int(i)for i in input().split()]
    tyo = tyo - {B-1}
    ko[A-1].append(B-1)
tyo =list(tyo)
tyouten =tyo[0]
rank =[[-1,-1]for _ in range(N)]
def keisan(num,no,bef):
    if rank[num][0] < no:
        rank[num]=[no,bef]
    for i in ko[num]:
        keisan(i,no+1,num)

keisan(tyouten,0,-1)
for i in rank:
    print(i[1]+1)

### FIXED CODE ###

import queue
N,M =[int(i)for i in input().split()]
adlist =[[]for i in range(N)] #隣接リスト
oyalist =[[]for i in range(N)] #親ノードリスト
for _ in range(N+M-1):
    A,B =[int(i)-1 for i in input().split()]
    adlist[A].append(B)
    oyalist[B].append(A)

iri =[0]*N #入次数のリスト
for i in range(N):
    iri[i] =len(oyalist[i])

topo =[0]*N #トポロジカルソートの番号
tyouten =oyalist.index([]) #頂点
num = 0 #ソート番号
q =queue.Queue()
q.put(tyouten)
topo[tyouten]=num

while num != N-1:
    now = q.get()
    for i in adlist[now]:
        iri[i] -=1
        if iri[i] == 0:
            q.put(i)
            num += 1
            topo[i] =num

#出力
oyalist[tyouten].append(-1)
for i in range(N):
    oyalist[i] =sorted(oyalist[i],key=lambda x:topo[x],reverse=True)
    print(oyalist[i][0]+1)
### BUGGY CODE ###

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

area = h*w
ans = 0
for i in range(1,area+1):
  if i%2 == 1:
    ans += 1

print(ans)

### FIXED CODE ###

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

if w == 1:
  print(1)
  exit()
if h == 1:
  print(1)
  exit()
if w%2 == 0:
  ans = w//2 * h
elif w%2 == 1:
  if h%2 == 0:
    ans = h*w//2
  elif h%2 == 1:
    ans = h*w//2 + 1

print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
dp = [-1] * (W + 1)
dp[0] = 0
for _ in range(N):
  w, v = map(int, input().split())
  for i in range(W - w, -1, -1):
    dpi = dp[i]
    if dpi != -1:
      if dp[i + w] < dpi + v:
        dp[i + w] = dpi + v
print(max(dp))

### FIXED CODE ###

def dynamicprogramming():
  N, W = map(int, input().split())
  dp = [-1] * (W + 1)
  dp[0] = 0
  for _ in range(N):
    w, v = map(int, input().split())
    for i in range(W - w, -1, -1):
        dpi = dp[i]
        if dpi != -1:
          if dp[i + w] < dpi + v:
            dp[i + w] = dpi + v
  print(max(dp))

dynamicprogramming()
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

n,m = nm()
h = nl()
path = [[False]*n for _ in range(n)]

for i in range(n):
    path[i][i] = True 

for i in range(m):
    a,b = nm()
    path[a-1][b-1] = path[b-1][a-1] = True

res = 0
for i,j in enumerate(path):
    temp = []
    for k,l in enumerate(j):
        if l:
            temp.append(h[k])
    ma = max(temp)
    if temp.count(ma) == 1 and  ma == h[i]:
        res += 1

print(res)

### FIXED CODE ###


n,m = map(int, input().split(' '))
h = list(map(int, input().split(' ')))
a = [list(map(int, input().split(' '))) for _ in range(m)]

res = [set() for _ in range(n)]

for i,j in a:
    res[i-1].add(j-1)
    res[j-1].add(i-1)
ans = 0
res = [j if j != set() else set([i]) for i,j in enumerate(res)]
for i in range(n):
    for j in res[i]:
        if i == j:
            ans += 1
            break
        if h[i] <= h[j]:
            break
    else:
        ans += 1
print(ans)
### BUGGY CODE ###

import math
from collections import defaultdict

n, m = [int(i) for i in input().split()]

A = defaultdict(int)
p = 10 ** 9 + 7

i = 2

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(30+10**5)
invf = invfact(30+10**5, f)

def comb(a, b):
    return f[a] * invf[b] * invf[a-b] % p

while m != 1:
    while m % i == 0:
        m //= i
        A[i] += 1
    i += 1

n -= 1
ans = 1

for v in A.values():
    ans *= comb(v+n, n)
    ans %= p

print(ans)

### FIXED CODE ###

import math
from collections import defaultdict

n, m = [int(i) for i in input().split()]

A = defaultdict(int)
p = 10 ** 9 + 7

if m == 1:
    print(1)
    exit()

def fact(n, p=10**9 + 7):
    f = [1]
    for i in range(1, n+1):
        f.append(f[-1]*i%p)
    return f

def invfact(n, f, p=10**9 + 7):
    inv = [pow(f[n], p-2, p)]
    for i in range(n, 0, -1):
        inv.append(inv[-1]*i%p)
    return inv[::-1]

f = fact(30+10**5)
invf = invfact(30+10**5, f)

def comb(a, b):
    return f[a] * invf[b] * invf[a-b] % p

i = 2

while m != 1 and i <= math.sqrt(m) + 1:
    while m % i == 0:
        m //= i
        A[i] += 1
    i += 1

if not A:
    print(n)
    exit()

if m != 1:
    A[m] = 1

n -= 1
ans = 1

for v in A.values():
    ans *= comb(v+n, n)
    ans %= p

print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = set()
for i in range(n-1,-1,-1):
    c = 0
    for v in ans:
        if v%(i+1)==0:
            c+=1
    if a[i] ==0 and c%2==1:
        ans.add(i+1)
    if a[i] == 1 and c % 2 == 0:
        ans.add(i + 1)
ret = list(ans)
ret.sort()
print(len(ret))
print(*ret)

### FIXED CODE ###

import sys,math
n = int(input())
a = list(map(int,input().split()))
select = [0 for _ in range(n+1)]
mark = [0 for _ in range(n+1)]
c = 0
for i in range(n-1,0,-1):
    if a[i] ==0 and mark[i+1]%2==1:
        c += 1
        select[i + 1] = 1
        l = 1
        r = (i + 1)
        m = math.sqrt(i+1)
        m = int(m)
        while (l <=m):
            if (i + 1) % l == 0:
                mark[l] += 1
                r = (i + 1) // l
                if l != r:
                    mark[r] += 1
            l += 1
    if a[i] and mark[i+1]%2==0:
        c+=1
        select[i + 1] = 1
        l = 1
        r = (i + 1)
        m = math.sqrt(i + 1)
        m = int(m)
        while (l <= m):
            if (i + 1) % l == 0:
                mark[l] += 1
                r = (i + 1) // l
                if l!=r:
                    mark[r] += 1
            l += 1
if a[0]==0 and mark[1]%2==1:
    c+=1
    select[1]=1
    mark[1]+=1
elif a[0]==1 and mark[1]%2==0:
    c += 1
    select[1] = 1
    mark[1] += 1
print(c)
for i in range(1,n+1):
    if select[i]:
        sys.stdout.write('{} '.format(i))
### BUGGY CODE ###

def main():
	N, K, L = map(int, input().split())
	road = [0]*K
	rail = [0]*L
	road_graph = [[] for _ in range(N+1)]
	rail_graph = [[] for _ in range(N+1)]
	ans_list = [""]*N
	for i in range(K):
		road[i] = list(map(int, input().split()))
		road_graph[road[i][0]].append(road[i][1])
		road_graph[road[i][1]].append(road[i][0])
	for i in range(L):
		rail[i] = list(map(int, input().split()))
		rail_graph[rail[i][0]].append(rail[i][1])
		rail_graph[rail[i][1]].append(rail[i][0])

	def dfs(start, graph):
		this_ans = set()
		stack = []
		stack.extend(graph[start])
		this_ans.add(start)
		while stack:
			cur = stack.pop()
			if cur in this_ans:
				continue
			this_ans.add(cur)
			stack.extend(graph[cur])
		return this_ans

	appeared = set()
	for i in range(1, N+1):
		if i in appeared:
			continue
		both_connected = dfs(i, road_graph) & dfs(i, rail_graph)
		this_ans = str(len(both_connected))
		for city in both_connected:
			ans_list[city-1] = this_ans
			appeared.add(city)

	ans = " ".join(ans_list)
	print(ans)


if __name__ == '__main__':
	main()

### FIXED CODE ###

from collections import defaultdict
def main():
	N, K, L = map(int, input().split())
	road = [0]*K
	rail = [0]*L
	road_graph = [[i, 0] for i in range(N+1)]
	rail_graph = [[i, 0] for i in range(N+1)]

	def root(graph, i):
		parent = graph[i][0]
		if parent == i:
			return i
		return root(graph, parent)

	def is_same_tree(graph, i, j):
		return root(graph, i) == root(graph, j)

	def unite(graph, i, j):
		if is_same_tree(graph, i, j):
			return
		l = graph[root(graph, i)]
		r = graph[root(graph, j)]
		if l[1] < r[1]:
			l[0] = r[0]
			r[1] += 1
		else:
			r[0] = l[0]
			l[1] += 1

	ans_list = [""]*N

	for i in range(K):
		road[i] = list(map(int, input().split()))
		unite(road_graph, road[i][0], road[i][1])
	for i in range(L):
		rail[i] = list(map(int, input().split()))
		unite(rail_graph, rail[i][0], rail[i][1])

	ans_memo = defaultdict(int)
	road_memo = [0]*(N+1)
	rail_memo = [0]*(N+1)
	for i in range(1, N+1):
		road_root = root(road_graph, i)
		rail_root = root(rail_graph, i)
		road_memo[i] = road_root
		rail_memo[i] = rail_root
		ans_memo[(road_root, rail_root)] += 1

	for i in range(1, N+1):
		road_root = road_memo[i]
		rail_root = rail_memo[i]
		this_ans = str(ans_memo[road_root, rail_root])
		ans_list[i-1] = this_ans

	ans = " ".join(ans_list)
	print(ans)


if __name__ == '__main__':
	main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    H, W, D = LI()
    mod_array = [[0 for _ in range(H*W//D+1)] for _ in range(D)]
    for row_number in range(H):
        row = LI()
        for column_number, item in enumerate(row):
            mod_array[item%D][item//D] = (row_number, column_number)

    # print(mod_array)

    Q = II()
    for _ in range(Q):
        L, R = LI()
        ans = 0
        prev_position = mod_array[L%D][L//D]
        for position in mod_array[L%D][L//D+1:R//D+1]:
            ans += abs(prev_position[0] - position[0]) + abs(prev_position[1] - position[1])
            prev_position = position
        print(ans)
        


main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    H, W, D = LI()
    mod_array = [[(0,0) for _ in range(H*W//D+1)] for _ in range(D)]
    for row_number in range(H):
        row = LI()
        for column_number, item in enumerate(row):
            mod_array[item%D][item//D] = (row_number, column_number)

    # print(mod_array)

    mod_array_cumsum = [[0 for _ in range(H*W//D+1)] for _ in range(D)]
    for row_number in range(D):
        cumsum = 0
        prev_position = mod_array[row_number][0]
        for column_number in range(1, H*W//D+1):
            position = mod_array[row_number][column_number]
            cumsum += abs(prev_position[0] - position[0]) + abs(prev_position[1] - position[1])
            mod_array_cumsum[row_number][column_number] = cumsum
            prev_position = position

    # print(mod_array_cumsum)

    Q = II()
    for _ in range(Q):
        L, R = LI()
        ans = mod_array_cumsum[L%D][R//D] - mod_array_cumsum[L%D][L//D]
        print(ans)
        

main()
### BUGGY CODE ###

def function(p, i):
  a = p[i]
  amin = min(p[:i+1])
  if amin == a:
    return 1
  else:
    return 0

n = int(input())
p = list(map(lambda x: int(x), input().split()))
sums = sum([function(p,i) for i in range(n)])
print(sums)

### FIXED CODE ###

n = int(input())
p = list(map(lambda x: int(x), input().split()))
 
count = 0
maxs = p[0]
for i in range(n):
  if maxs >= p[i]:
    maxs = p[i]
    count += 1
print(count)
### BUGGY CODE ###

line1 = input().split()
n = int(line1[0])
k = int(line1[1])
a = [int(ai) for ai in input().split()]

route = [0]
for j in range(k):
  now = a[route[j]] - 1
  if now in route:
    break
  else:
    route.append(now)

l_start = route.index(now)
print(route[l_start + ((k - l_start) % (len(route) - l_start))] + 1)

### FIXED CODE ###

line1 = input().split()
n = int(line1[0])
k = int(line1[1])
a = [int(ai) for ai in input().split()]

route = [0]
use = {0}
for j in range(k):
  now = a[route[j]] - 1
  if now in use:
    break
  else:
    route.append(now)
    use.add(now)

l_start = route.index(now)
print(route[l_start + ((k - l_start) % (len(route) - l_start))] + 1)
### BUGGY CODE ###

#入力
HWD = list(map(int, input().split()))
H, W, D = HWD[0], HWD[1],  HWD[2]
field = []
for i in range(H):
    field.append(list(map(int, input().split())))

#numberからD動かした時の魔力
move_dict = {}
pre_length = 0
for now_point in range(1, H * W + 1):
    pre_point = now_point - D
    if now_point > D:
        if now_point - D > D:
            pre_length = move_dict[now_point - D]
        for field_h in range(H):
            for field_w in range(W):
                if field[field_h][field_w] == pre_point:
                    pre_h = field_h
                    pre_w = field_w
                    pre_flag = True
                if field[field_h][field_w] == now_point:
                    now_h = field_h
                    now_w = field_w
                    now_flag = True
        move_dict[now_point] = abs(now_h - pre_h) + abs(now_w - pre_w) + pre_length
    else:
        move_dict[now_point] = 0
           
#試験
Q = int(input())
for test in range(Q):
    target = list(map(int, input().split()))
    count = move_dict[target[1]] - move_dict[target[0]]
    print(count) 

### FIXED CODE ###

#入力
HWD = list(map(int, input().split()))
H, W, D = HWD[0], HWD[1],  HWD[2]
field_dict = {}
for h in range(H):
    field = list(map(int, input().split()))
    for w in range(W):
        field_dict[field[w]] = (h, w)

#numberからD動かした時の魔力
move_dict = {}
pre_length = 0
for now_point in range(1, H * W + 1):
    pre_point = now_point - D
    if now_point > D:
        pre_length = move_dict[now_point - D]
        now_h = field_dict[now_point][0]
        now_w = field_dict[now_point][1]
        pre_h = field_dict[pre_point][0]
        pre_w = field_dict[pre_point][1]
        move_dict[now_point] = abs(now_h - pre_h) + abs(now_w - pre_w) + pre_length
    else:
        move_dict[now_point] = 0
           
#試験
Q = int(input())
for test in range(Q):
    target = list(map(int, input().split()))
    count = move_dict[target[1]] - move_dict[target[0]]
    print(count)