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

N = int(input())

def check_753(N):
    num = [0 for _ in range(10)]
    for i in range(len(N)):
        num[int(N[i])] = 1
    if sum(num) == 3:
        if num[3]+num[5]+num[7] == 3:
            return True
        else:
            return False
    else:
        return False

count = 0
for i in range(N):
    count += int(check_753(str(i+1)))
print(count)


### FIXED CODE ###

N = input()
k = len(N)
N = int(N)

nums = ['3', '5', '7']
add3 = lambda x: x + '3'
add5 = lambda x: x + '5'
add7 = lambda x: x + '7'

cnt = 0
for _ in range(k-1):
    num_tmp = []
    num_tmp.append(list(map(add3, nums)))
    num_tmp.append(list(map(add5, nums)))
    num_tmp.append(list(map(add7, nums)))
    nums = sum(num_tmp, [])

    for i in range(len(nums)):
        if '3' in nums[i] and '5' in nums[i] and '7' in nums[i] and int(nums[i]) <= N:
            cnt += 1

print(cnt)
### BUGGY CODE ###

n = int(input())
s = input()

a = []
b = set()
b.add("")
c=[b.copy()]
for i in range(n - 1, -1, -1):
    for j, k in enumerate(a):
        a[j] = s[i] + k
    a.append(s[i])
    b |= set(a)
    c.append(b.copy())
c.reverse()

a = []
b = set()
b.add("")
d = [b.copy()]
for i in range(n):
    for j, k in enumerate(a):
        a[j] = k+s[i]
    a.append(s[i])
    b |= set(a)
    d.append(b.copy())
ans = 0

for i, j in zip(c, d):
    e = len(max(i & j, key=len))
    ans = max(e, ans)
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
dp = [[0] * (n + 1) for _ in range(n + 1)]
ans = 0
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        if s[i] == s[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
            ans = max(ans, min(abs(i - j), dp[i][j]+1))
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(4100000)

lis =[]
abc =[]
count = 0

N = int(input())
for _ in range(N):
    lis.append(input())

for i in lis:
    if any(i == j for j in abc):
        pass
    else:
        abc.append(i)
        count += 1

print(count)
    

### FIXED CODE ###

n = int(input())

ans = len(set(input() for i in range(n)))

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

s = input()
t = input()

S = "abcdefghijklmnopqrstuvwxyz"

A = [[] for k in range(26)]
for k in range(len(s)):
    A[S.index(s[k])].append(k+1)

ans = 0
now = 0
for k in range(len(t)):
    if len(A[S.index(t[k])]) == 0:
        print(-1)
        exit(0)
    if max(A[S.index(t[k])]) <= now:
        ans += len(s)
        now = min(A[S.index(t[k])])
    else:
        for l in range(len(A[S.index(t[k])])):
#            print(A[S.index(t[k])][l]>now)
            if A[S.index(t[k])][l] > now:
                now = A[S.index(t[k])][l]
                break
print(ans+now)


### FIXED CODE ###

import sys
from bisect import bisect_right as bisect
def main():
    input = sys.stdin.readline
    s = input()[:-1]
    t = input()[:-1]
#    S = "abcdefghijklmnopqrstuvwxyz"
    A = [[] for k in range(26)]
    for k in range(len(s)):
        A[ord(s[k])-97] += [k+1]
    ans = 0
    now = 0
    for k in range(len(t)):
        a = ord(t[k]) - 97
        if len(A[a]) == 0:
            print(-1)
            exit(0)
        if A[a][-1] <= now:
            ans += len(s)
            now = A[a][0]
        else:
            now = A[a][bisect(A[a],now)]
    print(ans+now)

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


import numpy as np
nl = lambda: list(map(int, input().split()))
s = lambda: input()

H, W = nl()
grid = []
for i in range(H):
    grid.append(s())


yoko = np.zeros((H, W), dtype=np.uint64)
for row in range(H):
    count = 0
    for col in range(W):
        if grid[row][col] == '.':
            count += 1
            yoko[row][col] = count
        else:
            count = 0

    count = 0
    for col in range(W-1, -1, -1):
        if yoko[row][col] > 0:
            count = max(count, yoko[row][col])
            yoko[row][col] = count
        else:
            count = 0

tate = np.zeros((H, W), dtype=np.uint64)
for col in range(W):
    count = 0
    for row in range(H):
        if grid[row][col] == '.':
            count += 1
            tate[row][col] = count
        else:
            count = 0

    count = 0
    for row in range(H-1, -1, -1):
        if tate[row][col] > 0:
            count = max(count, tate[row][col])
            tate[row][col] = count
        else:
            count = 0

res = 0
for row in range(H):
    for col in range(W):
        res = max(res, yoko[row][col] + tate[row][col] - 1)

print(int(res))




### FIXED CODE ###

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

H, W = nl()
grid = []
for i in range(H):
    grid.append(s())

ups = [[0]*W for j in range(H)]
downs = [[0]*W for j in range(H)]
lefts = [[0]*W for j in range(H)]
rights = [[0]*W for j in range(H)]

for col in range(W):
    p = 0
    for row in range(H):
        if grid[row][col] == '#':
            p = 0
        else:
            p += 1
        ups[row][col] = p

    p = 0
    for row in range(H-1, -1, -1):
        if grid[row][col] == '#':
            p = 0
        else:
            p += 1
        downs[row][col] = p

for row in range(H):
    p = 0
    for col in range(W):
        if grid[row][col] == '#':
            p = 0
        else:
            p += 1
        lefts[row][col] = p

    p = 0
    for col in range(W-1, -1, -1):
        if grid[row][col] == '#':
            p = 0
        else:
            p += 1
        rights[row][col] = p

res = 0
for row in range(H):
    for col in range(W):
        res = max(res, ups[row][col] + downs[row][col] + lefts[row][col] + rights[row][col] -3)
print(res)
### BUGGY CODE ###

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

n = int(input())
a = []
b = []
b2 = []
c = []
count = 0

for i in range(n):
    x,y = list(map(int,input().split()))
    a.append([x,y,x+y])

a.sort(key=lambda x: x[2])

for i in a:
    c = b.copy()
    b.extend(list(range(i[0]-i[1], i[0]+i[1])))
    b2 = b.copy()
    b = list(set(b))
    if len(b2) != len(b):
        b = c.copy()
        count += 1
    
print(n - count)

### FIXED CODE ###

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

n = int(input())
a = []
b = []
b2 = []
c = []
count = 0
max = 0

for i in range(n):
    x,y = list(map(int,input().split()))
    a.append([x,y,x+y])

a.sort(key=lambda x: x[2])

for i in a:
    if max != 0 and i[0]-i[1] < max:
        count += 1
    else:
        max = i[2]
    
print(n - count)
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split()))
ans=0
for i in range(n-1):
    for j in range(i,n):
        if j-i == a[j]+a[i]:
            ans+=1


print(ans)


### FIXED CODE ###

import collections
n=int(input())
a=list(map(int, input().split()))
ans=0
b=[]
c=[]
for i in range(n):
    b.append(i+a[i])
    c.append(i-a[i])
b=collections.Counter(b)
c=collections.Counter(c)
for i in range((10**5)*2):
    ans+=b[i]*c[i]



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

N = int(input())
L = list(map(int,input().split()))
L.sort()

c=0
for i in range (N-2):
    for j in range (i+1,N-1):
        for k in range (j+1,N):
            if L[i]+L[j] > L[k]: #and L[j]+L[k] > L[i] and L[k]+L[i] > L[j]:
                c += 1
            else:
                break

print(c)

### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()
c = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        zum = L[i]+L[j]
        start = j+1
        goal = N-1
        now = (start + goal)//2

        if zum > L[goal]:
            c += goal - j
        elif zum <= L[start]:
            c += 0
        else:
            while not L[now] < zum <= L[now+1]:
                now = (start + goal)//2
                if zum > L[now]:
                    start = now
                else:
                    goal = now
            c += now - j

print(c)
### BUGGY CODE ###

N,M=map(int,input().split())
ps=[list(input().split()) for _ in range(M)]

a=[]
b=[]
count=0

for j in range(M):
    if ps[j][1]=="WA":
        if ps[j][0] not in b:
            a.append(ps[j][0])
    elif ps[j][1]=="AC":
        if ps[j][0] not in b:
            b.append(ps[j][0])

for i in range(len(b)):
    count+=a.count(b[i])

print(len(b),count)

### FIXED CODE ###

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

AC=[0]*N
WA=[0]*N
ac=0
wa=0

for i in range(M):
    p,s=map(str,input().split())
    P=int(p)
    if s=="AC":
        if AC[P-1]!=P:
            AC[P-1]+=P
            ac+=1
            wa+=WA[P-1]
    else:
        if AC[P-1]!=P:
            WA[P-1]+=1

print(ac,wa)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
S=0
i=N
while i>1:
    saidai=A.index(max(A[0:i]))
    S+=sum(list(map(lambda x:max(A[0:i])-x,A[saidai:i])))
    i=saidai
print(S) 

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
s=a[0]
ans=0
for i in range(n):
    if a[i]<s:
        ans+=s-a[i]
    else:
        s=a[i]
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
from collections import defaultdict
g = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

w = defaultdict(int)
for _ in range(Q):
    p, x = map(int, input().split())
    w[p] += x
    
ans = [0] * (N + 1)

visited = defaultdict(bool)
def dfs(i):
    stack = []
    visited[i] = True
    stack.append(i)
    while len(stack) != 0:
        v = stack.pop()
        W = w[v]
        ans[v] += W
        for c in g[v]:
            if not visited[c]:
                visited[c] = True
                stack.append(c)
                ans[c] += ans[v]

dfs(1)
print(*ans[1:])

### FIXED CODE ###

N, Q = map(int, input().split())
from collections import defaultdict
g = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

w = defaultdict(int)
for _ in range(Q):
    p, x = map(int, input().split())
    w[p] += x
    
ans = [0] * (N + 1)

visited = defaultdict(bool)
stack = []
visited[1] = True
stack.append(1)
while len(stack) != 0:
    v = stack.pop()
    W = w[v]
    ans[v] += W
    for c in g[v]:
        if not visited[c]:
            visited[c] = True
            stack.append(c)
            ans[c] += ans[v]

print(*ans[1:])
### BUGGY CODE ###

import math


def solve():
    A, B, N = map(int, input().split())

    ans = 0
    div_ab = A/B
    div_1b = 1/B
    init_1 = (max(1, N-100000)*A)/B
    init_2 = max(1, N-100000)/B
    start = max(1, N-100000)

    for i in range(max(1, N-100000), N + 1):
        ans = max(math.floor(init_1+div_ab*(i-start)) - A*math.floor(init_2+div_1b*(i-start)),ans)
    if N > B:
        start = max(B-100000,1)
        init_1 = (max(1, int(B-100000)) * A) / B
        init_2 = max(1, int(B-100000)) / B
        for i in range(max(int(B)-100000,1), max(N,int(B)+1)):
            ans = max(math.floor(init_1 + div_ab * (i - start)) - A * math.floor(init_2 + div_1b * (i - start)), ans)

    print(int(ans))


if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve():
    A,B,N = map(int, input().split())
    if N < B-1:
        print((A*N)//B - A * (N//B))
    else:
        print(((A*(B-1))//B) - A* ((B-1)//B))


if __name__ == "__main__":
    solve()
### BUGGY CODE ###

n,k = map(int, input().split())
ps = list(map(int, input().split()))
ans = 0
max_ps = 0
start = 0

ps_k = [sum(ps[i:i+k]) for i in range(n)]

start = ps_k.index(max(ps_k))

print(sum([sum(range(i+1))/i for i in ps[start:start+k]]))

### FIXED CODE ###

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

tmp = sum(ps[:k])
max_ps = tmp
start = 0

for i in range(1,n-k+1):
    tmp = tmp-ps[i-1]+ps[i+k-1]
    if tmp >= max_ps:
        max_ps = tmp
        start = i

print(sum([(i*(i+1))/ (2*i) for i in ps[start:start+k]]))
### BUGGY CODE ###

K, S = map(int, input().split())
count = 0

for i in range(0 ,K + 1):
	for j in range(0 ,K + 1):
		for k in range(0, K +1):
			if S == i + j + k:
				count += 1

print(str(count))

### FIXED CODE ###

K, S = map(int, input().split())
count = 0

for i in range(0 ,K + 1):
	for j in range(0 ,K + 1):
		z = S - i - j
		if z >= 0 and z <= K:
			count += 1

print(str(count))
### BUGGY CODE ###

import copy
n = int(input())
x=list(map(int,input().split()))
for i in range(n):
  l=copy.copy(x)
  l.pop(i)
  l.sort()
  print(l[n//2-1])
  

### FIXED CODE ###

import copy
n = int(input())
x=list(map(int,input().split()))
l=copy.copy(x)
l.sort()
n1 = l[n//2-1]
n2 = l[n//2]
for i in range(n):
  if x[i]>n1:
    print(n1)
  else:
    print(n2)
### BUGGY CODE ###

a,b = input().split(' ')
a = int(a)
b = int(b)

ans = 100000000000
check = False

for i in range(a, b):
    if check:
        break
    for j in range(i + 1, b + 1):
        if (i * j) % 2019 < ans:
            ans = (i * j) % 2019

print(ans)


### FIXED CODE ###

a,b = input().split(' ')
a = int(a)
b = int(b)
 
ans = 100000000000
 
for i in range(a, min(b, a + 2019)):
    for j in range(i + 1, min(b + 1, a + 2019)):
        if (i * j) % 2019 < ans:
            ans = (i * j) % 2019
 
print(ans)
### BUGGY CODE ###

import heapq

def dijkstra(ad_lst, n, s, t):
    costs = [float('inf') for i in range(n+1)]
    costs[s] = 0
    Q = []
    heapq.heappush(Q, [costs[s], s])

    while(Q != []):
        c, u = heapq.heappop(Q)
        for v, c in ad_lst[u]:
            alt = costs[u] + c
            if alt < costs[v]:
                heapq.heappush(Q, [alt, v])
                costs[v] = alt

    return costs

n,m,s,t, = map(int, input().split())

route_y = {i: [] for i in range(n+1)}
route_s = {i: [] for i in range(n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    route_y[u].append([v,a])
    route_y[v].append([u,a])
    route_s[u].append([v,b])
    route_s[v].append([u,b])

cost_y = dijkstra(route_y, n, s, t)
cost_s = dijkstra(route_s, n, t, s)
cost_ys = [y+s for y, s in zip(cost_y, cost_s)]
result = [float('inf') for _ in range(n+1)]
min_cost = result[-1]
for i in range(n, 0, -1):
    if min_cost > cost_ys[i]:
        min_cost = cost_ys[i]
    result[i] = min_cost
yen = 10**15
for i in range(1, n+1):
    print(yen - result[i])


### FIXED CODE ###

import heapq
from itertools import accumulate
inf = float('inf')

def dijkstra(ad_lst, n, s):
    costs = [inf for i in range(n+1)]
    costs[s], Q = 0, []
    heapq.heappush(Q, [costs[s], s])

    while(Q != []):
        c, u = heapq.heappop(Q)
        for v, c in ad_lst[u].items():
            if costs[u] + c < costs[v]:
                heapq.heappush(Q, [costs[u] + c, v])
                costs[v] = costs[u] + c

    return costs

n,m,s,t, = map(int, input().split())

route_y = {i: {} for i in range(n+1)}
route_s = {i: {} for i in range(n+1)}
for i in range(m):
    u, v, a, b = map(int, input().split())
    route_y[u][v] = a
    route_y[v][u] = a
    route_s[u][v] = b
    route_s[v][u] = b

cost_y = dijkstra(route_y, n, s)
cost_s = dijkstra(route_s, n, t)
result = list(accumulate([y+s for y,s in zip(cost_y, cost_s)][::-1], min))
yen = 10**15
[print(yen-result[i]) for i in range(n-1, -1, -1)]
### BUGGY CODE ###

A, B, K = map(int, input().split(' '))

tmp_list = [i for i in range(A, B + 1)]
tmp_list2 = []

for i in tmp_list[0 : K]:
    tmp_list2.append(i)
    print(i)

for i in tmp_list[len(tmp_list) - K:]:
    if i not in tmp_list2:
        print(i)

### FIXED CODE ###

A, B, K = map(int, input().split(' '))

if (B - A + 1) / 2 < K:
    for i in range(A, B + 1):
        print(i)
else:
    for i in range(A, A + K):
        print(i)
    for i in range(B - K + 1, B + 1):
        print(i)
### BUGGY CODE ###

town_graph = {}
road_graph = {}

N,M,L = list(map(int, input().split()))
# N = num towns
# M = num roads
# L = fuel tank capacity

for _ in range(M):
    A,B,C = list(map(int, input().split()))
    if not A in town_graph:
        town_graph[A] = [B]
    else:
        town_graph[A].append(B)
    if not B in town_graph:
        town_graph[B] = [A]
    else:
        town_graph[B].append(B)

    road_graph[tuple(sorted([A,B]))] = C
    road_graph[tuple([A,A])] = 0
    road_graph[tuple([B,B])] = 0

Q = int(input())
queries = []
for _ in range(Q):
    queries.append(list(map(int,input().split())))

#print(town_graph)
#print(road_graph)

# initialize remaining road_graph distances:
for i in range(1, N+1):
    for j in range(1, N+1):
        key = tuple(sorted([i,j]))
        if not key in road_graph:
            road_graph[key] = float('inf')

# use flord warshall to find min path between all towns
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if road_graph[tuple(sorted([i,j]))] > road_graph[tuple(sorted([i,k]))] + road_graph[tuple(sorted([k,j]))]:
                road_graph[tuple(sorted([i,j]))] = road_graph[tuple(sorted([i,k]))] + road_graph[tuple(sorted([k,j]))]

#print(road_graph)

# if the two towns can be travelled to on one tank, add to our fuel graph with distance 1
fuel_graph = road_graph.copy()
for town_pair in road_graph:
    if road_graph[town_pair] <= L:
        fuel_graph[town_pair] = 1
    else:
        fuel_graph[town_pair] = float('inf')

#print(road_graph)
#print(fuel_graph)

# use flord warshall to find min number of fuel tanks to travel between two towns
for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if fuel_graph[tuple(sorted([i,j]))] > fuel_graph[tuple(sorted([i,k]))] + fuel_graph[tuple(sorted([k,j]))]:
                fuel_graph[tuple(sorted([i,j]))] = fuel_graph[tuple(sorted([i,k]))] + fuel_graph[tuple(sorted([k,j]))]
#print(fuel_graph)
for query in queries:
    num_tanks = fuel_graph[tuple(sorted(query))] - 1
    if num_tanks != float('inf'):
        print(num_tanks)
    else:
        print("-1")


### FIXED CODE ###

from scipy.sparse.csgraph import floyd_warshall

N,M,L = list(map(int, input().split()))

edges = [[0] * N for _ in range(N)]

for _ in range(M):
    A,B,C = list(map(int, input().split()))
    edges[A-1][B-1] = C
    edges[B-1][A-1] = C

Q = int(input())
queries = []

for _ in range(Q):
    queries.append(list(map(int,input().split())))

# use flord warshall to find min path between all towns
edges = floyd_warshall(edges)

# if the two towns can be travelled to on one tank, add to our fuel graph with distance 1
for i in range(N):
    for j in range(N):
        if edges[i][j] <= L:
            edges[i][j] = 1
        else:
            edges[i][j] = 0

# use flord warshall to find min number of fuel tanks to travel between two towns
edges = floyd_warshall(edges)

for query in queries:
    s = query[0] - 1
    t = query[1] - 1
    num_tanks = edges[s][t] - 1
    if num_tanks != float('inf'):
        print(int(num_tanks))
    else:
        print("-1")
### BUGGY CODE ###

n = int(input())
a = list(input().split())
l = [str(i) for i in range(1, n+1)]

for i in range(n):
  print(a.count(l[i]))

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
ans = [0]*n

for i in a:
  ans[i-1] += 1
for j in ans:
  print(j)
### BUGGY CODE ###

import sys 
sys.setrecursionlimit(100000)
INF = 10000000000
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]

def dfs(x, y, m):
    if mem[x][y][m] != INF:
        return mem[x][y][m]
    if y > N :
        return 0
    n = INF
    for j in range(2 if m > 0 else 1):
        for i, s in enumerate(st[y + 1 + j]):
            srip = max(0, st[y][x][1] + s[1])
            l = abs(st[y][x][0] - s[0])
            n = min(dfs(i, y + 1 + j, m - j) + srip * l, n)
    mem[x][y][m] = n
    return mem[x][y][m]

while True:
    mem = [[[INF for i in range(200)] for j in range(200)] for k in range(200)]
    N, M = map(int, input().split())
    if N == 0:
        break
    st = [[[-INF, -INF]] for i in range(N + 3)]
    for s in st[1:-2]:
        v = list(map(int, input().split()))
        del s[0]
        for i in range(1, len(v), 2):
            s.append([v[i], v[i + 1]])
    print(dfs(0, 0, M))

### FIXED CODE ###

INF = 10000000000
dx = [0, 0, 1, -1]
dy = [-1, 1, 0, 0]
 
def dfs(x, y, m):
    if y > N :
        return 0
    if mem[x][y][m] != INF:
        return mem[x][y][m]
    n = INF
    for j in range(2 if m > 0 else 1):
        for i, s in enumerate(st[y + 1 + j]):
            srip = max(0, st[y][x][1] + s[1])
            l = abs(st[y][x][0] - s[0])
            n = min(dfs(i, y + 1 + j, m - j) + srip * l, n)
    mem[x][y][m] = n
    return mem[x][y][m]
 
while True:
    N, M = map(int, raw_input().split())
    if N == 0:
        break
    st = [[[-INF, -INF]] for i in range(N + 3)]
    for s in st[1:-2]:
        v = list(map(int, raw_input().split()))
        del s[0]
        for i in range(1, len(v), 2):
            s.append([v[i], v[i + 1]])
    mem = [[[INF for i in range(M + 1)] for j in range(N + 1)] for k in range(N + 4)]
    print(dfs(0, 0, M))
### BUGGY CODE ###

h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]

iti = [[] for _ in range(h*w + 1)]

for h_ in range(h):
    for w_ in range(w):
        iti[a[h_][w_]].append(w_+1)
        iti[a[h_][w_]].append(h_+1)

#累積和的なやつ
s_d = [[0]*(h*w + 1) for _ in range(d+1)]
for i in range(1, d+1):
    now = i
    while now + d <= h*w:
        s_d[i][now + d] = s_d[i][now] + abs(iti[now][0]-iti[now+d][0]) + abs(iti[now][1]-iti[now+d][1])
        now += d
#print(s_d)


def query(l, r):
    idx = l % d
    if idx == 0:
        idx = d
    cost = s_d[idx][r] - s_d[idx][l]
    return cost


q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(query(l, r))


### FIXED CODE ###

h, w, d = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(h)]

iti = [[] for _ in range(h*w + 1)]

for h_ in range(h):
    for w_ in range(w):
        iti[a[h_][w_]].append(w_+1)
        iti[a[h_][w_]].append(h_+1)

#累積和的なやつ
s_d = [[] for _ in range(d+1)]
for i in range(1, d+1): # i:= スタート位置　1からｄまである
    now = i
    s_d[i].append(0) # スタート位置のコストは０
    while now + d <= h*w:
        s_d[i].append(s_d[i][-1] + abs(iti[now][0]-iti[now+d][0]) + abs(iti[now][1]-iti[now+d][1]))
        now += d
#print(s_d)

def query(l, r):
    idx = l % d # スタート位置 = idx　
    if idx == 0:
        idx = d
    # s_d[idx]の配列を使用
    # l, rをs_d[idx]上のインデックスに合わせる
    l_d = l // d
    r_d = r // d
    if l % d == 0:
        l_d -= 1
        r_d -= 1
    cost = s_d[idx][r_d] - s_d[idx][l_d]
    return cost


q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(query(l, r))
### BUGGY CODE ###

# ABC158
# D - String Formation

def ChangeState(Is_normal):
    if Is_normal==True:
        return False
    else:
        return True



S=input()
Q=int(input())
Is_normal=True

for _ in range(Q):
    q = list(map(str,input().split()))
    if len(q)== 1 :
        Is_normal = ChangeState(Is_normal)
    else:
        if q[1]=='1':
            if Is_normal==True:
                S=q[2]+S
            else :
                S=S+q[2]
        else :
            if Is_normal==True:
                S=S+q[2]
            else:
                S=q[2]+S
    # print(Is_normal, S)
if Is_normal==False:
    S=S[::-1]
print(S)


### FIXED CODE ###

# ABC158
# D - String Formation

def ChangeState(Is_normal):
    if Is_normal==True:
        return False
    else:
        return True



S=input()
Q=int(input())
Is_normal=True

h=''
t=[]

for _ in range(Q):
    q = input()
    if len(q)== 1 :
        Is_normal = ChangeState(Is_normal)
    else:
        if q[2]=='1':
            if Is_normal==True:
                h=h+q[4]
            else :
                S=S+q[4]
        else :
            if Is_normal==True:
                S=S+q[4]
            else:
                h=h+q[4]
    # print(Is_normal, S)
h=h[::-1]
S=h+S
if Is_normal==False:
    S=S[::-1]
print(S)
### BUGGY CODE ###

s = input()
m = int(input())

c = []

for i in range(len(s)):
    for k in range(1,len(s)+1):
        c.append(s[i:i+k])

b = sorted(list(set(c)))

print(b[m-1])


### FIXED CODE ###

s = input()
m = int(input())

c = []


for i in range(len(s)):
    for k in range(1,m+1):
        c.append(s[i:i+k])

b = sorted(list(set(c)))


print(b[m-1])