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

N,M=map(int,input().split())
E=[[] for i in range(N)]
for i in range(M):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  E[u].append(v)
S,T=map(int,input().split())
S,T=S-1,T-1

stack=[]
INF=10**9
seen=[[INF for i in range(3)] for j in range(N)]
stack.append([S,0,1])
ans=INF
while stack:
  node=stack.pop()
  v=node[0]
  step=node[1]
  turn=node[2]
  if step==3:
    if v==T:
      if ans>turn:
        ans=turn
      continue
    step=0
    turn+=1
  if seen[v][step]<=turn:
    continue
  seen[v][step]=turn
  children=E[v]
  for child in children:
    stack.append([child,step+1,turn])
else:
  if ans==INF:
    print(-1)
  else:
    print(ans)


### FIXED CODE ###

N,M=map(int,input().split())
E=[[] for i in range(N)]
for i in range(M):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  E[u].append(v)
S,T=map(int,input().split())
S,T=S-1,T-1

from collections import deque
stack=deque()
seen=[[False for i in range(3)] for j in range(N)]
stack.append([S,0,1])
while stack:
  node=stack.popleft()
  v=node[0]
  step=node[1]
  turn=node[2]
  if step==3:
    if v==T:
      print(turn)
      break
    step=0
    turn+=1
  if seen[v][step]:
    continue
  seen[v][step]=True
  children=E[v]
  for child in children:
    stack.append([child,step+1,turn])
else:
  print(-1)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(N // R + 1):
    if N - r * R < 0:
        break
    for g in range(N // G + 1):
        tmp = N - r * R - g * G
        if tmp < 0:
            break
        if tmp % B == 0 and tmp // B >= 0:
            ans += 1

print(ans)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(N // R + 1):
    for g in range((N - R * r) // G + 1):
        tmp = N - r * R - g * G
        if tmp % B == 0:
            ans += 1

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

n, m = list(map(int, input().split()))
row1 = list(map(int, input().split()))
lis = list(range(row1[0], row1[1]+1))
#print(lis)

for i in range(m-1):
  rowi = list(map(int, input().split()))
  rowi = list(range(rowi[0], rowi[1]+1))
  newlis = []
  for j in lis:
    #print(j)
    if j in rowi:
      newlis.append(j)
    #print(newlis)
  lis = newlis
      
print(len(lis))

### FIXED CODE ###

n, m = list(map(int, input().split()))
low =[]
high=[]

for i in range(m):
  temp = list(map(int, input().split()))
  low.append(temp[0])
  high.append(temp[1])
  
maxlow= max(low)
minhigh=min(high) 

if minhigh-maxlow >= 0:
  print(minhigh-maxlow+1)
else:
  print(0)
### BUGGY CODE ###

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

while True:
    if (H + W == 0) : break
    
    for i in range(H):
        print('#' * W)



### FIXED CODE ###

while True:
    H, W = map(int, input().split())

    if (H + W == 0) : break
    
    for i in range(H):
        print('#' * W)

    print()
### BUGGY CODE ###

def main():
    import bisect
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    f = list(map(int, input().split()))
    a.sort()
    f.sort(reverse = True)
    d = [[f[i]*a[i], f[i], a[i]] for i in range(n)]
    for i in range(k):
        if d[d.index(max(d))][2] > 0:
            d[d.index(max(d))][2] -= 1
            d[d.index(max(d))][0] -= d[d.index(max(d))][1]
        else:
            break
    print(d[d.index(max(d))][0])
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():

    import numpy as np
    
    n, k = map(int, input().split())
    a = np.array(input().split(), np.int64)
    f = np.array(input().split(), np.int64)
    a.sort()
    a = a[::-1]
    f.sort()
    right = np.max(a*f)
    left = 0
    while right > left:
        middle = (right + left)//2
        b = 0
        
        if np.sum(np.maximum(a-middle//f, 0)) <= k:
            right = middle
        else:
            left = middle+1

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

L, R = map(int,input().split())

a = 100000000000
for i in range(L,R + 1):
  for j in range(i + 1,R + 1):
    if a >= i * j % 2019:
      a = i * j % 2019
    elif a == 0:
      break
  

print(a)

### FIXED CODE ###

L, R = map(int,input().split())

a = 100000000000
for i in range(L,R + 1):
  if a == 0:
    break
  for j in range(i + 1,R + 1):
    if a >= i * j % 2019:
      a = i * j % 2019
      if a == 0:
        break
  

print(a)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
point = 0
while True:
	A =[x % 2 for x in a]
	if A.count(0) != len(a):
		break
	A = [x // 2 for x in a]
	point += 1
print(point)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
 
count = 0
flag = True
while flag:
    for i in range(len(a)):
        if a[i] % 2 == 1:
            flag = False
        else:
            a[i] //= 2
    count += 1
 
print(count - 1)
### BUGGY CODE ###

def main():
    s = input().split("T")
    x, y = map(int, input().split())
    xs = []
    x -= len(s[0])
    for i in range(2, len(s), 2):
        xs.append(len(s[i]))
    ys = []
    for i in range(1, len(s), 2):
        ys.append(len(s[i]))
    
    ok = False
    for i in range(2**len(xs)):
        tmp = 0
        for j in range(len(xs)):
            if i&1:
                tmp += xs[0]
            else:
                tmp -= xs[0]
            i >>= 1
        if tmp == x:
            ok = True
            break
    if ok:
        ok = False
        for i in range(2**len(ys)):
            tmp = 0
            for j in range(len(ys)):
                if i&1:
                    tmp += ys[0]
                else:
                    tmp -= ys[0]
                i >>= 1
            if tmp == y:
                ok = True
                break
    if ok:
        print("Yes")
    else:
        print("No")

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np

def main():
    s = input().split("T")
    x, y = map(int, input().split())
    xs = []
    x -= len(s[0])
    for i in range(2, len(s), 2):
        tmp = len(s[i])
        if tmp != 0:
            xs.append(tmp)
    ys = []
    for i in range(1, len(s), 2):
        tmp = len(s[i])
        if tmp != 0:
            ys.append(tmp)
    
    sum_x = sum(xs)
    sum_y = sum(ys)
    x = abs(x)
    y = abs(y)
    if sum_x < x or sum_y < y:
        print("No")
    else:
        rest_x = sum_x - x
        rest_y = sum_y - y
        if rest_x&1 or rest_y&1:
            print("No")
        else:
            ok = True
            if rest_x > 0:
                dp = np.array([[False]*8001 for i in range(len(xs)+1)])
                dp[0][0] = True
                for i in range(1, len(xs)+1):
                    dp[i] = dp[i] | dp[i-1]
                    dp[i][xs[i-1]:] = dp[i-1][xs[i-1]:] | dp[i-1][:-xs[i-1]]
                    # dp[i][:-xs[i-1]] = dp[i-1][:-xs[i-1]] | dp[i-1][xs[i-1]:]
                if not dp[-1][rest_x//2]:
                    ok = False
            if rest_y > 0:
                dp = np.array([[False]*8001 for i in range(len(ys)+1)])
                dp[0][0] = True
                for i in range(1, len(ys)+1):
                    dp[i] = dp[i] | dp[i-1]
                    dp[i][ys[i-1]:] = dp[i-1][ys[i-1]:] | dp[i-1][:-ys[i-1]]
                    # dp[i][:-ys[i-1]] = dp[i-1][:-ys[i-1]] | dp[i-1][ys[i-1]:]
                if not dp[-1][rest_y//2]:
                    ok = False
            if ok:
                print("Yes")
            else:
                print("No")
                    

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

def main():
  import sys
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  sx,sy,tx,ty=map(int,input().split())
  calc=lambda x,y:x*1000007+y
  b=[[-1]*(w+2)]
  for i in range(h):
    s=input()
    bb=[-1]
    for j in s:
      if j==".":bb.append(0)
      else:bb.append(-1)
    bb.append(-1)
    b.append(bb)
  b.append([-1]*(w+2))
  d=[]
  d.append(calc(sx,sy))
  s=set()
  for ss in d:
    x,y=divmod(ss,1000007)
    if calc(x,y)in s:
      s.discard(calc(x,y))
      continue
    if x==tx and y==ty:
      exit(print(b[x][y]))
    for i in range(1,k+1):
      if b[x-i][y]<=b[x][y] and b[x-i][y]!=0:break
      d.append(calc(x-i,y))
      if b[x-i][y]!=0:
        s.add(calc(x-i,y))
      b[x-i][y]=b[x][y]+1
    for i in range(1,k+1):
      if b[x+i][y]<=b[x][y] and b[x+i][y]!=0:break
      d.append(calc(x+i,y))
      if b[x+i][y]!=0:
        s.add(calc(x+i,y))
      b[x+i][y]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
      d.append(calc(x,y-j))
      if b[x][y-j]!=0:
        s.add(calc(x,y-j))
      b[x][y-j]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
      d.append(calc(x,y+j))
      if b[x][y+j]!=0:
        s.add(calc(x,y+j))
      b[x][y+j]=b[x][y]+1
  print(-1)
if __name__ == "__main__":
  main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w,k=map(int,input().split())
si,sj,ti,tj=map(int,input().split())
si-=1
sj-=1
ti-=1
tj-=1
b=[input()for _ in range(h)]
ans=[[-1]*w for _ in range(h)]
ans[si][sj]=0
from collections import deque
d=deque()
d.append((si,sj))
while d:
  x,y=d.popleft()
  if x==ti and y==tj:
    exit(print(ans[x][y]))
  for dx,dy in [[1,0],[-1,0],[0,-1],[0,1]]:
    for i in range(1,k+1):
      xx=x+dx*i
      yy=y+dy*i
      if not(0<=xx<h and 0<=yy<w) or b[xx][yy]=="@":break
      if 0<=ans[xx][yy]<=ans[x][y]:break
      if ans[xx][yy]==-1:d.append((xx,yy))
      ans[xx][yy]=ans[x][y]+1
print(-1)
### BUGGY CODE ###


# ===== Main ==== #
def main():
    # =Input Space = #
    listA=[]
    while True:
        try:
            listA.append(list(map(int,input().split())))
        except:
            break;
    N = listA[0][0]
    A = listA[1]
    B = listA[2]

    if sum(A) < sum(B):
        print(-1)
        return 0
    C = []
    for i in range(len(A)):
        num = A[i] - B[i]
        C.append(num)
    D = C.copy()
    change_list = [i for i in C if i < 0]
    change_count = len(change_list)

    while True:
        if len([i for i in change_list if i < 0]) == 0:
            break
        max_ = max(C)
        max_index = C.index(max_)
        count = -1
        for i in change_list:
            count += 1
            if i < 0:
                if max_ <= abs(i):
                    change_list[count] += max_
                    max_ = 0
                    break
                else:
                    change_list[count] = 0
                    max_ -= abs(i)
        C[max_index] = max_
        change_count += 1

    print(change_count)


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

    if sum(A) < sum(B):
        return -1

    C = [a-b for a,b in zip(A,B)]
    plus = [x for x in C if x > 0]
    minus = [x for x in C if x < 0]
    change = sum(minus)
    count = 0
    if change == 0:
        return 0

    for i in sorted(plus,reverse=True):
        if change >= 0:
            break
        change += i
        count += 1
    return count + len(minus)

print(solve())
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [float("inf")] * n
dp[0] = 0
for i in range(1, n):
  if i < k:
    dp[i] = min([ dp[j]+abs(h[j]-h[i]) for j in range(i) ])
  else:
    dp[i] = min( [ dp[i-j-1]+abs(h[i-j-1]-h[i]) for j in range(k) ] )
print(dp[n-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [float("inf")] * n
dp[0] = 0
for i in range(1, n):
  if i < k:
    dp[i] = min([ dp[j]+abs(h[j]-h[i]) for j in range(i) ])
  else:
    dp[i] = min( [ dp[i-j-1]+abs(h[i-j-1]-h[i]) for j in range(k) ] )
print(dp[n-1])
### BUGGY CODE ###

# C - gacha

n = int(input())
s = []

for i in range(n):
    gacha = input()
    if gacha not in s:
        s.append(gacha)

print(len(s))


### FIXED CODE ###

# C - gacha

n = int(input())
s = []
c = 1

for i in range(n):
    s.append(input())

s.sort()

for j in range(1,n):
    if s[j-1] != s[j]:
        c += 1


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

import bisect

N = int(input())
A = [0] * N
for i in range(N):
  A[i] = int(input())

B = [A[0]]
for i in range(1, N):
  if A[i] <= B[0]:
    B.insert(0, A[i])
  else:
    index = bisect.bisect_left(B, A[i]) - 1
    B[index] = A[i]
print(len(B))

### FIXED CODE ###

import bisect

N = int(input())
A = [0] * N
for i in range(N):
  A[i] = int(input())

B = [A[N - 1]]
for i in reversed(range(0, N - 1)):
  if A[i] >= B[-1]:
    B.append(A[i])
  else:
    index = bisect.bisect_right(B, A[i])
    B[index] = A[i]
print(len(B))
### BUGGY CODE ###

import math
import sys

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

def C(N,P):
    if N == 1: return P
    a=P
    N1=2
    while N >= N1:
        N1*=2
        a=math.sqrt(a)

    res=1
    for i in range(1,int(a)+2):
        if P % i**N: continue
        res = i
    return res

print(C(n,p))

### FIXED CODE ###

n,p = list(map(int,input().split())) 
i = a = o = 1
m = round(p**(1/n))
for i in range(m,0,-1):
    a = i**n
    if p%a==0:
        print(i)
        exit()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n,m,r= map(int, input().split())
rr= list(map(int, input().split()))
a= [list(map(int, input().split())) for i in range(m)]
edges=[[] for i in range(n)]

for x,y,z in a:
    edges[x-1].append((y-1,z))
    edges[y-1].append((x-1,z))

#ダイクストラ法
from heapq import heappush, heappop

def dijkstra(edges, size, source,g):
    # edge=探索するグラフ
    # size=グラフの点の数
    # source=スタート点
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance[g]

# bit DP
# dp[S][v]: 訪れた点の集合がSで最後にVを訪れた時のVのMIN
INF=float('inf')
dp=[[INF]*r for i in range(1<<r)]
dp[0]=[0]*r

for i in range(1<<r):
    for k in range(r):
        # 訪問リストに入っているものを最後に訪問する時
        if (i >> k) & 1:
            if i^(1<<k)==0:
                dp[i][k]=0
            else:
                # 最後に訪れるものを除いた集合でどこを最後に訪問した時がminか調べる
                for l in range(r):
                    if (i ^ (1 << k))>>l:
                        dpm = dp[i ^ (1 << k)][l]
                        ad = dijkstra(edges, n, rr[l] - 1, rr[k] - 1)
                        dp[i][k] = min(dpm + ad, dp[i][k])

print(min(dp[-1]))

### FIXED CODE ###

import sys
input = sys.stdin.readline

n,m,r= map(int, input().split())
rr= list(map(int, input().split()))
a= [list(map(int, input().split())) for i in range(m)]
d=[[float('inf')]*n for i in range(n)]
for i in range(n):
    d[i][i]=0

for i,j,k in a:
    i-=1
    j-=1
    d[i][j]=k
    d[j][i]=k


# ワーシャルフロイド　全点最短経路、負の距離あっても可　o(n**3)
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])

    return d
d=warshall_floyd(d)


# bit DP
# dp[S][v]: 訪れた点の集合がSで最後にVを訪れた時のVのMIN
INF=float('inf')
dp=[[INF]*r for i in range(1<<r)]
dp[0]=[0]*r

for i in range(1<<r):
    for k in range(r):
        # 訪問リストに入っているものを最後に訪問する時
        if (i >> k) & 1:
            if i^(1<<k)==0:
                dp[i][k]=0
            else:
                # 最後に訪れるものを除いた集合でどこを最後に訪問した時がminか調べる
                for l in range(r):
                    if (i ^ (1 << k))>>l:
                        dpm = dp[i ^ (1 << k)][l]
                        ad = d[rr[l] - 1][ rr[k] - 1]
                        dp[i][k] = min(dpm + ad, dp[i][k])

print(min(dp[-1]))
### BUGGY CODE ###

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

data = [[0]*W for i in range(H)]
c = 0
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            data[i][j] = 1
            c += 1

if c == H*W:
    print(0)
    exit()

ans = 0
while True:
    ans += 1
    for h in range(H):
        for w in range(W):
            if data[h][w] == ans:
                if 0 < h:
                    if data[h-1][w] == 0:
                        data[h-1][w] = ans + 1
                        c += 1
                if h < H-1:
                    if data[h+1][w] == 0:
                        data[h+1][w] = ans + 1
                        c += 1
                if 0 < w:
                    if data[h][w-1] == 0:
                        data[h][w-1] = ans + 1
                        c += 1
                if w < W-1:
                    if data[h][w+1] == 0:
                        data[h][w+1] = ans + 1
                        c += 1
    if c >= H*W:
        break
print(ans)


### FIXED CODE ###

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

data = [[-W]*W for i in range(H)]

for i in range(H):
    s = input()
    x = -(2*W)
    for j in range(W):
        if s[j] == '#':
            x = 0
        data[i][j] = x
        x += 1
    x = -(2*W)
    for j in range(W):
        if data[i][W-j-1] == 0:
            x = 0
        elif data[i][W-j-1] < 0:
            data[i][W-j-1] = x
        else:
            if x > 0:
                x = min(x, data[i][W-j-1])
            else:
                x = data[i][W-j-1]
            data[i][W-j-1] = x
        x += 1


for w in range(W):
    x = -(2*H)
    for h in range(H):
        if data[h][w] == 0:
            x = 0
        elif data[h][w] > 0:
            if x > 0:
                x = min(x, data[h][w])
            else:
                x = data[h][w]
            data[h][w] = x
        else:
            data[h][w] = x
        x += 1
    x = -(2*H)
    for h in range(H):
        if data[H-h-1][w] == 0:
            x = 0
        elif data[H-h-1][w] > 0:
            if x > 0:
                x = min(x, data[H-h-1][w])
            else:
                x = data[H-h-1][w]
            data[H-h-1][w] = x
        else:
            data[H-h-1][w] = x
        x += 1

ans = 0
for d in data:
    ans = max(ans, max(d))
print(ans)
### BUGGY CODE ###

#/usr/bin/env python
from functools import *
from math import *

n = int(input())
a = list(map(int, input().split()))

gcds = []
for i in range(n):
    tmp = a[:i] + a[i+1:]
    g = reduce(gcd, tmp)
    gcds.append(g)

print(max(gcds))


### FIXED CODE ###

#/usr/bin/env python
from functools import *
from math import *

n = int(input())
a = list(map(int, input().split()))

gcds = []
lgcd = []
rgcd = [0 for _ in range(n)]
l = r = 0 
for i in range(n):
    if i == 0:
        l = 0 
    else:
        l = gcd(l, a[i-1])
    lgcd.append(l)

for i in range(n):
    if i == 0:
        r = 0 
        rgcd[n-1] = r 
    else:
        r = gcd(r, a[n-i])
        rgcd[n-i-1] = r 

for i in range(n):
    g = gcd(lgcd[i], rgcd[i])
    gcds.append(g)

print(max(gcds))
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
a.sort()
c.sort()
c = c[::-1]
x,y,answer = [],[],0
for j in b:
	for k in range(n):
		if a[k] >= j:
			x.append(k)
			break
		elif k == n-1:
			x.append(n)
	for k2 in range(n):
		if c[k2] <= j:
			y.append(k2)
			break
		elif k2 == n-1:
			y.append(n)
for i in range(n):
	 answer += x[i]*y[i]
print(answer)


### FIXED CODE ###

import bisect
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
a.sort()
c.sort()
answer = 0
for i in b:
	x = bisect.bisect_right(c,i)
	y = bisect.bisect_left(a,i)
	answer += (n-x)*y
print(answer)
### BUGGY CODE ###

a = int(input())
ans = 1
n = list(map(int, input().split()))
for i in range(a):
    ans = ans * n[i]
    if n[i] == 0:
        ans = 0
        break
print(ans if ans <= 10**18 else -1)

### FIXED CODE ###

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

cnt=0
S=str(input())
m=[0]*len(S)
L=len(S)

for i in range(L):
    m[i]=int(S[L-1-i:])%2019
    if m[i]==0:cnt+=1
    for j in range(L-i,L):
        if m[i]==m[L-1-j]:
            cnt+=1 
print(cnt)


### FIXED CODE ###

S=input()
mc=[0]*2019

tg=0
digit=1
for s in S[::-1]:
    tg+=int(s)*digit
    mc[tg%2019]+=1
    digit=digit*10%2019

ans=sum(m*(m-1)//2 for m in mc)
print(ans+mc[0])
### BUGGY CODE ###

n, a, b = map(int, input().split())
res = 0

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
#N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

    
#res = cmb(n,3,mod)
for i in range(1, n+1):
    res += cmb(n,i,mod)
res -= cmb(n,a,mod)
res -= cmb(n,b,mod)

print(res)

### FIXED CODE ###

n, a, b = map(int, input().split())

mod = 10**9 + 7
res = pow(2, n, mod)

def cmb(n, r, mod):
    r = min(n-r, r)
    if r == 0:
        return 1
    over, under = 1, 1
    for i in range(1, r+1):
        over = over * (n-i+1) % mod
        under = under * i % mod
    inv = pow(under, mod-2, mod)
    return over * inv % mod


A = cmb(n, a, mod)
B = cmb(n, b, mod)

print((res - A - B - 1) % mod)
### BUGGY CODE ###

s = list(input())
K = int(input())

l =[]
l2 = []

for i in range(len(s)):
    tmp = ''
    for j in range(i, len(s)):
        if j > i + 4: break
        tmp += s[j]
        l.append(tmp)
l.sort()

for i in l:
    is_double = 0
    for j in l2:
        if j == i:
            is_double = 1
            break
    if is_double == 0:
        l2.append(i)

ans = l2[K - 1]

print(ans)


### FIXED CODE ###

s = list(input())
K = int(input())

l =[]

for i in range(len(s)):
    tmp = ''
    for j in range(i, len(s)):
        if j > i + 4: break
        tmp += s[j]
        l.append(tmp)
l.sort()

l2 = []
for x in l:
    if len(l2) > 6:
        break
    if x not in l2:
        l2.append(x)


ans = l2[K - 1]

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

import time
import random
N = int(input())
s = str(input())
maxlen = N//2
start = time.time()
def solve(tgt):
    for i in range(N-tgt*2+1):
        if s[i:i+tgt] in s[i+tgt:]:
            return True
    return False

ng = maxlen + 1
ok = 0
if N>650:
    ok = 2
first = 1
while ng-ok > 1:
    end = time.time()
    if end-start > 1.8:
        r = random.random.randint(ok,ng-1)
        print(r)
        exit()
    tgt = (ok+ng)//2
    if first == 1:
        tgt == tgt*7//8
        first = 0
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)


### FIXED CODE ###

from collections import defaultdict as dd
N = int(input())
s = str(input())
maxlen = N//2

def solve(tgt):
    dic = dd(int)
    st = s[tgt:2*tgt]
    dic[st] += 1
    ls = [st]
    for char in s[2*tgt:]:
        st = st[1:]+char
        dic[st] += 1
        ls.append(st)
    st = s[:tgt]
    if dic[st] > 0:
        return True
    dic[ls[0]] -= 1
    for i,char in enumerate(s[tgt:N-tgt]):
        st = st[1:]+char
        if dic[st] > 0:
            return True
        dic[ls[i+1]] -= 1
    return False

ng = maxlen + 1
ok = 0
while ng-ok > 1:
    tgt = (ok+ng)//2
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)