Harryxun/stf_run huggingface dataset:
a = int(input())
b = int(input())
c = int(input())
x = int(input())

count = 0
for i in range(a+1):
 if 500*i>x: break
 for j in range(b+1):
  if x-500*i-100*j > 50*c: break
   count += 1

print(count)

### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
x = int(input())

count = 0
for i in range(a+1):
 for j in range(b+1):
  for k in range(c+1):
   if 500*i+100*j+50*k == x:
    count += 1

print(count)
def dfs_a(N,v,adjlist,cur):
    global depth_a
    depth_a[v]=cur
    for node in adjlist[v]:
        if depth_a[node]<0:
            dfs_a(N,node,adjlist,cur+1)
def dfs_t(N,v,adjlist,cur):
    global depth_t
    depth_t[v]=cur
    for node in adjlist[v]:
        if depth_t[node]<0:
            dfs_t(N,node,adjlist,cur+1)
    
    
    

from collections import deque

N,u,v=map(int,input().split())
adjlist=[[] for _ in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    adjlist[a-1].append(b-1)
    adjlist[b-1].append(a-1)
depth_a=[-1]*N
depth_t=[-1]*N
dfs_a(N,v-1,adjlist,0)
dfs_t(N,u-1,adjlist,0)
M=0
for i in range(N):
    if depth_a[i]>depth_t[i]:
        curm=depth_a[i]-1
        if curm>M:
            M=curm
print(M)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

def dfs_a(N,v,adjlist,cur):
    global depth_a
    depth_a[v]=cur
    for node in adjlist[v]:
        if depth_a[node]<0:
            dfs_a(N,node,adjlist,cur+1)
def dfs_t(N,v,adjlist,cur):
    global depth_t
    depth_t[v]=cur
    for node in adjlist[v]:
        if depth_t[node]<0:
            dfs_t(N,node,adjlist,cur+1)
    
    
    

from collections import deque

N,u,v=map(int,input().split())
adjlist=[[] for _ in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    adjlist[a-1].append(b-1)
    adjlist[b-1].append(a-1)
depth_a=[-1]*N
depth_t=[-1]*N
dfs_a(N,v-1,adjlist,0)
dfs_t(N,u-1,adjlist,0)
M=0
for i in range(N):
    if depth_a[i]>depth_t[i]:
        curm=depth_a[i]-1
        if curm>M:
            M=curm
print(M)
import sys
A, B, K = map(int, input().split())
box = list(range(A, B+1))
if 2*K < len(box):
    box.sort()
    for i in box:
        print(i)
    sys.exit()
if A == B:
    if K >= 1:
        print(A)
        sys.exit()
    else:
        print()
        sys.exit()
box.sort()
temp1 = box[:K] + box[-K:]
temp = sorted(set(temp1), key=temp1.index)
temp.sort()
for i in temp:
    print(i)

### FIXED CODE ###

A, B, K = map(int, input().split())
L = [A+i for i in range(K) if A+i <= B]
R = [B-i for i in range(K) if B-i >= A]
S = set(L+R)
S = sorted(S)
for v in S:
    print(v)
import math
a = math.pi
x = int(raw_input())

print x*x*a,2*x*a

### FIXED CODE ###

import math
a = math.pi
r = float(raw_input())

print "%f %f" % (r * r * a, 2 * r * a)
import math

N = int(input())

min_cand = 10**9

for i in range(1,(int(math.sqrt(N))+1):
  if N % i == 0 and min_cand < (i + (N // i)):
    min_cond = (i + (N // i))
    
print(min_cond - 2)
    

### FIXED CODE ###

import math
 
N = int(input())
 
min_cand = 10**12
 
for i in range(1,(int(math.sqrt(N))+1)):
  if N % i == 0 and min_cand > (i + (N // i)):
    min_cand = (i + (N // i))
    
print(min_cand - 2)
n, k = map(int, input().split())

a = [int(x)-1 for x in input().split()]

v = []
b = 0
stop = -1

for i in range(n):
    if b not in v:
        v.append(b)
        b = a[b]
    else:
        stop = v.index(b)
        break

v1 = v[:stop]
v2 = v[stop:]
c1 = len(v1)
c2 = len(v2)

if k>c1:
    r = (k-c1)%c2
else:
    r = k
    
print(v[stop+r]+1)



### FIXED CODE ###

n, k = map(int, input().split())

a = [int(x)-1 for x in input().split()]

v = []
vc = [0]*n
b = 0
c = 0

while True:
    if vc[b]>0:
        stop = v.index(b)
        break
    v.append(b)
    vc[b] += 1
    b = a[b]
    c += 1



if k>stop:
    r = (k-stop)%(c-stop)
    print(v[stop+r]+1)
else:
    print(v[k]+1)
n = int(input())
i = 1

while True:
    x = i
    if  x % 3 == 0:
        print(" %d" ,i)
        i+=1
        if i > n:
            print()
            break
    if x % 10 == 3:
        print(" %d" ,i)
        i+=1
        if i > n:
            print()
            break
    else:
        x /= 10
        if x != 0
        continue


### FIXED CODE ###

#
# 5d
#

def main():
    n = int(input())
    s = ""
    for i in range(1, n+1):
        x = i
        if x % 3 == 0 or x % 10 == 3:
            s += " " + str(i)
        else:
            x //= 10
            while x:
                if x % 10 == 3:
                    s += " " + str(i)
                    break
                x //= 10
    print(s)


if __name__ == '__main__':
    main()
a = int(input())
# スペース区切りの整数の入力
b = input().split()
b = [int(i) for i in b]

c = len(b)
d = 0


while c == len(b):
  c=0
  for i in b:
    if b %2 == 0:
      c +=1
  if(c == len(a)):
    d += 1
    b = [b /2 for i in b]
print (d)
   




### FIXED CODE ###


a = int(input())
# スペース区切りの整数の入力
b = input().split()
b = [int(i) for i in b]

c = len(b)
d = 0


while c == len(b):
  c=0
  for i in b:
    if i %2 == 0:
      c +=1
  if(c == len(b)):
    d += 1
    b = [i/2 for i in b]
print (d)
x = int(raw_input())
print(x**3)

### FIXED CODE ###

x = input()
y = int(x)
print(y**3)
H,K=map(int,input().split())
lst_0=list(map(int,input().split()))
DP[0]=0
lst_2=[]
for i in range(1,H):
    lst_1=[]
    for j in range(1,K+1):
        if i - j >= 0:
            DP[i]=abs(lst_0[i]-lst_0[i-j])+DP[i-j]
            lst_1.append(DP[i])
    DP[i]=min(lst_1)
print(DP[-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
H, K = map(int, input().split())
lst_0=list(map(int,input().split()))
DP=[float("INF")]*H
DP[0]=0
for i in range(1,H):
    for j in range(1,K+1):
        if i - j >= 0:
            DP[i]=min(DP[i],abs(lst_0[i]-lst_0[i-j])+DP[i-j])
print(DP[H-1])
a, b, k = [int(m) for m in input().split(" ")]

nums = range(a, b+1) if b-a <= k else list(range(a, a+k)) + list(range(b+1-k, b+1))
nums.sort()
for num in nums:
    print(num)

### FIXED CODE ###

a, b, k = [int(m) for m in input().split(" ")]

for i in range(a, min(a+k, b+1)):
    print(i)
for i in range(max(b+1-k, a+k), b+1):
    print(i)
k=int(input())
if n%2==0:
    print(n*n/4)
else:
    print((n-1)*(n+1)/4)

### FIXED CODE ###

n=int(input())
if n%2==0:
    print(int((n*n)/4))
else:
    print(int(((n-1)*(n+1))/4))
cnt = 0
l_sort = []
for i in range(n):
    if sorted(l[i]) in l_sort:
        cnt += 1
    l_sort.append(sorted(l[i]))

print(cnt)

### FIXED CODE ###

N = int(input())
s = [input() for i in [0]*N]
words = {}
cnt = 0
for i in s:
    i = "".join(sorted(i))
    time = words.get(i,0)
    cnt += time
    words[i] = time + 1
print(cnt)
n, k = list(map(int, input().split()))
h = list(map(int, input().split()))
inf = 10 ** 4+1
dp = [inf] * n
dp[0] = 0
for i in range(n):
    dp[i] = min([dp[i - j]  + abs(h[i - j] - h[i]) for j in range(max(0,i-k),i))])
print(dp[-1])


### FIXED CODE ###

n, k = list(map(int, input().split()))
h = list(map(int, input().split()))
inf = 10 ** 4 + 1
dp = [inf] * n
dp[0] = 0
for i in range(1,n):
    H = h[i]
    dp[i] = min([dp[j] + abs(h[j] - H) for j in range(max(0, i - k), i)])
print(dp[-1])
l,r=map(int,input().split())
if r-l>=2019:
  print(0)
else:
  a=2019
  for i in range(l,r):
    for j in range(i+1,r+1):
      if i==l and j=i+1:
        a=min((i%2019)*(j%2019)%2019,a)
print(a)

### FIXED CODE ###

l,r=map(int,input().split())
if r-l>=2019:
  print(0)
else:
  a=2019
  for i in range(l,r):
    for j in range(i+1,r+1):
      a=min((i%2019)*(j%2019)%2019,a)
  print(a)
n = input()
a = list(map(int,input().split()))
ans = 1
for i in a:
  ans *=i
  if ans>10**18:
  ans = -1
  break

print(ans)

### FIXED CODE ###

n = input()
a = list(map(int,input().split()))
ans = 1
t = False

for i in a:
  if i == 0:
    ans = 0
    t = True

if t != True:
  for i in a:
    ans *=i
    if ans>10**18:
      ans = -1
      break
    
print(ans)
from collections import defaultdict
INF = 9999999999999999999999999999

def spanning_tree(G):
  n = len(G)
  T = {}
  added = set()
  min_c = INF
  for i in G:
    for j in G[i]:
      if G[i][j] < min_c:
        min_c = G[i][j]
        min_e = (i, j)
  T[min_e] = min_c
  added.add(min_e[0])
  added.add(min_e[1])
  while len(added) < n:
    min_c = INF
    for u in added:
      for v in G[u]:
        if v in added:
          continue
        if G[u][v] < min_c:
          min_c = G[u][v]
          min_e = (u, v)
    T[min_e] = min_c
    added.add(min_e[1])
  return T


G = {}

n, m = [int(v) for v in input().strip().split(' ')]
for i in range(n):
  G[i] = {}
for _ in range(m):
  s, t, c = [int(v) for v in input().strip().split(' ')]
  G[s][t] = c
  G[t][s] = c

T = spanning_tree(G)

s = 0
for e in T:
  s += T[e]

print(s)

### FIXED CODE ###

from collections import defaultdict
from heapq import heappush, heappop
INF = 9999999999999999999999999999

def spanning_tree(G):
  n = len(G)
  T = {}
  added = set([0])
  heap = []
  for v in G[0]:
    heappush(heap, (G[0][v], (0, v)))
  while len(added) < n:
    while True:
      c, e = heappop(heap)
      if e[1] not in added:
        break
    T[e] = c
    added.add(e[1])
    for v in G[e[1]]:
      heappush(heap, (G[e[1]][v], (e[1], v)))

  return T


G = {}

n, m = [int(v) for v in input().strip().split(' ')]
for i in range(n):
  G[i] = {}
for _ in range(m):
  s, t, c = [int(v) for v in input().strip().split(' ')]
  G[s][t] = c
  G[t][s] = c

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

T = spanning_tree(G)

s = 0
for e in T:
  s += T[e]

print(s)
print(s[0] + str(len(s)-2) + s[-1])

### FIXED CODE ###

n,m = map(int,input().split())
print((n-1)*(m-1))
N = int(input())

flag = 0

for i in range(26):
    for j in range(16):
      if j*4+j*7 == N:
        flag = 1

if flag == 1:
    print("Yes")
else
    print("No")


### FIXED CODE ###

N = int(input())

flag = 0

for i in range(26):
    for j in range(16):
      if i*4+j*7 == N:
        flag = 1

if flag == 1:
    print("Yes")
else:
    print("No")
import sys
input=sys.stdin.readline
import math
a,b,n=map(int,input().split())
for x in range(n+1):
    f=math.floor(a*x/b)-a*math.floor(x/b)
    m.append(f)
print(max(m))

### FIXED CODE ###

a,b,n=map(int,input().split())
import math
if n<b:
    m=math.floor(a*n/b)
else:
    e=b-1
    m=math.floor(a*e/b)
print(m)
class UnionFind:
    pairs = {}
    def __init__(self, n):
        for i in range(n):
            self.pairs[i] = i

    def set(self, s, t):
        if s in self.pairs and self.pairs[s] != s:
            self.pairs[t] = s
        else:
            self.pairs[s] = t

    def root(self, x):
        if self.pairs[x] == x:
            return x
        self.pairs[x] = self.root(self.pairs[x])
        return self.pairs[x]

def main():
    n, m = map(int, input().split())

    uf = UnionFind(n)
    for i in range(m):
        s, t = map(int,input().split())
        uf.set(s - 1, t - 1)
#    print(uf.pairs)
    root = []
    for i in range(n):
        root.append(uf.root(i))
 #       print(i, uf.root(i))
    single_root = set(root)

    print(len(single_root)-1)
main()


### FIXED CODE ###

class UnionFind:
    pairs = {}
    def __init__(self, n):
        for i in range(n):
            self.pairs[i] = i

    def set(self, s, t):
        if s in self.pairs and self.pairs[s] == s:
            self.pairs[s] = self.root(t)
        else:
            self.pairs[t] = self.root(s)

    def root(self, x):
        if self.pairs[x] == x:
            return x
        self.pairs[x] = self.root(self.pairs[x])
        return self.pairs[x]

    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry :
            return
        self.pairs[rx] = ry
    def same(self, x, y ):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            return True
        else:
            return False
        
def main():
    n, m = map(int, input().split())

    uf = UnionFind(n)
    pairs =[]
    for i in range(m):
        s, t = map(int,input().split())
        if uf.same(s-1, t-1) == False:
            uf.unite(s-1,t-1)
        #pairs.append([s-1,t-1])

    # pairs.sort()
    # for pair in pairs:
    #     uf.set(pair[0], pair[1])
    #
    # for pair in pairs:
    #     uf.set(pair[0], pair[1])

    root = []
    for i in range(n):
        root.append(uf.root(i))
 #       print(i, uf.root(i))
    single_root = set(root)

    print(len(single_root)-1)
main()
S = input()
N = len(S)
S = list(S.split("T"))
x, y = map(int, input().split())

X_command = sorted([len(i) for i in S[::2]], reverse=True)
Y_command = sorted([len(i) for i in S[1::2]], reverse=True)

dp_x = [[False] * N for i in range(N)]
dp_y = [[False] * N for i in range(N)]

if X_command:
    dp_x[0][X_command[0]] = True
    for i in range(1, len(X_command)):
        for xi in range(N):
            if xi + X_command[i] >= N:
                continue
            if xi-X_command[i] >= 0:
                dp_x[i][xi] = dp_x[i-1][xi-X_command[i]] or dp_x[i-1][xi+X_command[i]]
            else:
                dp_x[i][xi] = dp_x[i-1][xi+X_command[i]]

if Y_command:
    dp_y[0][Y_command[0]] = True
    for i in range(1, len(Y_command)):
        for yi in range(N):
            if yi + Y_command[i] >= N:
                continue
            if yi-Y_command[i] >= 0:
                dp_y[i][yi] = dp_y[i-1][yi-Y_command[i]] or dp_y[i-1][yi+Y_command[i]]
            else:
                dp_y[i][yi] = dp_y[i-1][yi+Y_command[i]]


x, y = max(x, -x), max(y, -y)

if dp_x[len(X_command)-1][x] and dp_y[len(Y_command)-1][y]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

S = input()
N = len(S)
S = list(S.split("T"))
x, y = map(int, input().split())

X_command = sorted([len(i) for i in S[::2]], reverse=True)
Y_command = sorted([len(i) for i in S[1::2]], reverse=True)

nx = X_command.pop(-1)
ny = 0

for xi in X_command:
    if nx > x:
        nx -= xi
    else:
        nx += xi

for yi in Y_command:
    if ny > y:
        ny -= yi
    else:
        ny += yi

if nx == x and ny == y:
    print("Yes")
else:
    print("No")
H,W=(int,input().split())
h,w=(int,input().split())
S=H*W
print(S-(H*w+W*h)+w*h)
#どうやっても想定と違う値が出る　後で考え直す


### FIXED CODE ###

H,W=map(int,input().split())
h,w=map(int,input().split())
S=H*W
Hw=H*w
Wh=W*h
wh=w*h
print(S-Hw-Wh+wh)
n, m = map(int, input().split())
A = sorted(map(int, input().split()))
C = []
for _ in range(m):
    b, c = map(int, input().split())
    C += [[-c, b]]
C = sorted(C)
p = 0
for cb in C:
    c, b = -cb[0], cb[1]
    for _ in range(b):
        if (p >= n) | (A[p] >= c):
            break
        else:
            A[p] = c
            p += 1
print(sum(A))

### FIXED CODE ###

n, m = map(int, input().split())
A = sorted(map(int, input().split()))
C = []
for _ in range(m):
    b, c = map(int, input().split())
    C += [[-c, b]]
C = sorted(C)
p = 0
for cb in C:
    c, b = -cb[0], cb[1]
    for _ in range(b):
        if (p >= n) | (A[min(p, n-1)] >= c):
            break
        else:
            A[p] = c
            p += 1
print(sum(A))
import sys
import queue

N = 3
f= ''.join(sys.stdin.readline().split())
f+= ''.join(sys.stdin.readline().split())
f+= ''.join(sys.stdin.readline().split())

dd = [[-1, 0], [0, -1], [1, 0], [0, 1]]

Q = queue.Queue()
V = dict()

Q.put([f,f.index('0'),0])
V[f] = True

while not Q.empty():
    u = Q.get()
    if u[0] == '123456780':  break
    sx, sy = u[1]//N, u[1]%N
    for dx, dy in dd:
        tx, ty = sx+dx, sy+dy
        if tx<0 or ty<0 or tx>=N or ty>=N: continue
        v = u[:]
        n1, n2 = u[1], tx*N+ty
        v[1] = n2
	if n1>n2: n1, n2 = n2, n1
        v[0] = v[0][0:n1]+v[0][n2]+v[0][n1+1:n2]+v[0][n1]+v[0][n2+1:]
        if not V.get(v[0], False):
            V[v[0]] = True
            v[2] += 1 # dir[r]                                                       
            Q.put(v)

print(u[2])



### FIXED CODE ###

import sys
import queue

N = 3

f = ''.join(sys.stdin.readline().split())
f += ''.join(sys.stdin.readline().split())
f += ''.join(sys.stdin.readline().split())

dd = [[-1, 0], [0, -1], [1, 0], [0, 1]]

Q = [[f,f.index('0'),0]]
V = { f: True }

while len(Q)>0:
    u = Q.pop(0)
    if u[0] == '123456780':  break
    sx, sy = u[1]//N, u[1]%N
    for dx, dy in dd:
        tx, ty = sx+dx, sy+dy
        if tx<0 or ty<0 or tx>=N or ty>=N: continue
        v = u[:]
        n1, n2 = u[1], tx*N+ty
        v[1] = n2
        if n1>n2: n1, n2 = n2, n1
        v[0] = v[0][0:n1]+v[0][n2]+v[0][n1+1:n2]+v[0][n1]+v[0][n2+1:]
        if not V.get(v[0], False):
            V[v[0]] = True
            v[2] += 1 # dir[r]                                                       
            Q.append(v)

print(u[2])
import math
a = list(map(int,input().split()))
b = list(map(int,input().split()))
if sum(b) >= a[0]
	print("Yes")
else
	print("No")
 

### FIXED CODE ###

a = [list(map(int,input().split())) for l in range(2)]

if sum(a[1]) >= a[0][0]:
    print("Yes")
else:
    print("No")
import sys
input = sys.stdin.readline
def main():
    N = input()
    N_l = list(N)
    m = int(N_l[-1])
    if m == 0 or m == 1 or m==6 or m==8:
        print("pon")
    elif m == 2 or m== 4 or m == 5 or m == 7 or m==9:
        print("hon")
    elif m == 3:
        print("bon")
if __name__ == "__main__":
    main()



### FIXED CODE ###


def main():
    N = input()
    N_l = list(N)
    m = int(N_l[-1])
    if m == 0 or m == 1 or m==6 or m==8:
        print("pon")
    elif m == 2 or m== 4 or m == 5 or m == 7 or m==9:
        print("hon")
    elif m == 3:
        print("bon")
if __name__ == "__main__":
    main()
N = int(input())
S = str(input())
if N < len(S):
    S = S[:N]+'...'
print(S)



### FIXED CODE ###

N = str(input())
N = int(N[-1])
if N in [2,4,5,7,9]:
    print('hon')
elif N in [0,1,6,8]:
    print('pon')
else:
    print('bon')
N,W = map(int,input().split())

v = [0] * N
w = [0] * N
for i in range(N):
    w[i],v[i] = map(int,input().split())

dp = [[0] * (W+1) for _ in range(N)]

for i in range(N):
    for j in range(1, W+1):
        if w[i] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],v[i]+dp[i-1][j-w[i]])

print(max(dp[N-1]))

### FIXED CODE ###

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

v = [0] * N
w = [0] * N
for i in range(N):
    w[i],v[i] = map(int,input().split())
sumv = sum(v)+1
dp = [[float('inf')] * (sumv) for _ in range(N+1)]
for i in range(N):
    dp[i][0] = 0
for i in range(1, N+1):
    for j in range(1, sumv):
        if v[i-1] > j:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(dp[i-1][j],w[i-1]+dp[i-1][j-v[i-1]])
ans = 0
for i in range(1, sumv+1):
    if dp[N][-i] <= W:
        ans = sumv - i
        break
print(ans)
A, P = map(int, input())
print((A*3+P)//2)

### FIXED CODE ###

A, P = map(int, input().split())
print((A*3+P)//2)
import sys

def main():
    N = int(input())
    D = map(lambda i: int(i), input().split(' '))
    maximum = 0
    ary = [0] * (N - 1)
    for d in D:
        ary[d] = ary[d] + 1
        if maximum < d:
            maximum = d
    answer = 1
    for i in range(maximum + 1):
        if i == 0:
            if ary[i] != 1:
                print(0)
                sys.exit()
        elif ary[i] == 0:
            print(0)
            sys.exit()
        else:
            answer = (answer * (ary[i - 1] ** ary[i])) // 998244353
    print(answer)

main()


### FIXED CODE ###

import sys

def main():
    N = int(input())
    D = list(map(lambda i: int(i), input().split(' ')))
    # N = 100000
    # D = [0]
    # for i in range(1, N):
    #     D.append(i)

    if D[0] != 0:
        print(0)
        sys.exit()

    ary = [0] * N
    for d in D:
        ary[d] = ary[d] + 1

    # 続いてなかったらNG
    zero = False
    for i in range(len(ary)):
        if ary[i] != 0 and zero is True:
            print(0)
            sys.exit()
        if ary[i] == 0 and zero is False:
            zero = True

    # 距離0は頂点1だけ
    if ary[0] != 1:
        print(0)
        sys.exit()

    answer = 1
    for i in range(1, len(ary)):
        for j in range(ary[i]):
            answer = (answer * ary[i - 1]) % 998244353
    print(answer)

main()
a,b,c.d = map(int,input().split())
while a>=0 and b>=0:
  b-=c
  d-=a
if a == 0 and b==0:
  print('Yes')
elif b == 0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

a,b,c,d = map(int,input().split())
while a>0 and b>0:
  a-=d
  c-=b

if a <= 0 and c<=0:
  print('Yes')
elif c <= 0:
  print('Yes')
else:
  print('No')
tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dictx ={}
dicty ={}
for i in range(H):
    tmp = input().split()
    for d in range(W):
        dictx[tmp[d]] = i
        dicty[tmp[d]] = d
result ={}
cost ={}
def calcost(R):
    if int(R)<=D:
        cost[R] = 0
        return 0
    else:
        costs = abs(dictx[R]-dictx[str(int(R)-D)]) + abs(dicty[R]-dicty[str(int(R)-D)])
        if str(int(R)-D) in cost:
            cost[R] = costs + cost[str(int(R)-D)]
            return cost[R]
        else:
            cost[R] = costs + calcost(str(int(R)-D))
            return cost[R]

for n in range(D+1,H*W+1):
    calcost(str(n))

Q = int(input())
for j in range(Q):
    tmpx = input()
    if tmpx in result:
        print(result[tmpx])
    else:
        tmp = tmpx.split()
        result[tmpx] = cost[tmp[1]]-cost[tmp[0]]
        print(result[tmpx])

### FIXED CODE ###

tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dictx ={}
dicty ={}
for i in range(H):
    tmp = input().split()
    for d in range(W):
        dictx[tmp[d]] = i
        dicty[tmp[d]] = d
cost ={}
def calcost(R):
    if int(R)<=D:
        cost[R] = 0
        return 0
    else:
        costs = abs(dictx[R]-dictx[str(int(R)-D)]) + abs(dicty[R]-dicty[str(int(R)-D)])
        cost[R] = costs + cost[str(int(R)-D)]
        return cost[R]

for n in range(1,H*W+1):
    calcost(str(n))
Q = int(input())
for j in range(Q):
    tmp = input().split()
    print(str(cost[tmp[1]]-cost[tmp[0]]))