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

def bfs_longest(x,y):
    queuex = [x]
    queuey = [y]
    queuedis = [0]
    looked = [[x,y]]
    ans = [0]
    while(len(queuex)):
        nowx = queuex.pop(0)
        nowy = queuey.pop(0)
        nowdis = queuedis.pop(0)
        search = [[nowx+1,nowy],[nowx-1,nowy],[nowx,nowy+1],[nowx,nowy-1]]
        for i in range(len(search)):
            if not (search[i] in looked):
                if maze[search[i][0]][search[i][1]] == ".":
                    queuex.append(search[i][0])
                    queuey.append(search[i][1])
                    queuedis.append(nowdis+1)
                    ans.append(nowdis+1)
                    looked.append([search[i][0],search[i][1]])
    return max(ans)

h,w = map(int,input().split())
maze = [["#" for _ in range(w+2)]for p in range(h+2)]
anchor = []
for i in range(h):
    data = str(input())
    for j in range(w):
        maze[i+1][j+1] = data[j]
        if data[j] == ".":
            anchor.append([i+1,j+1])

answer = 0
for i in range(len(anchor)):
    answer = max(bfs_longest(anchor[i][0],anchor[i][1]),answer)
print(answer)

### FIXED CODE ###

def bfs_longest(x,y):
    queuex = [x]
    queuey = [y]
    queuedis = [0]
    looked = [[x,y]]
    ans = [0]
    while(len(queuex)):
        nowx = queuex.pop(0)
        nowy = queuey.pop(0)
        nowdis = queuedis.pop(0)
        search = [[nowx+1,nowy],[nowx-1,nowy],[nowx,nowy+1],[nowx,nowy-1]]
        for i in range(len(search)):
            if not (search[i] in looked):
                if maze[search[i][0]][search[i][1]] == ".":
                    queuex.append(search[i][0])
                    queuey.append(search[i][1])
                    queuedis.append(nowdis+1)
                    ans.append(nowdis+1)
                    looked.append([search[i][0],search[i][1]])
    return ans[-1]

h,w = map(int,input().split())
maze = [["#" for _ in range(w+2)]for p in range(h+2)]
anchor = []
for i in range(h):
    data = str(input())
    for j in range(w):
        maze[i+1][j+1] = data[j]
        if data[j] == ".":
            anchor.append([i+1,j+1])

answer = 0
if (len(anchor)) == (h*w):
    print(h+w-2)
    exit()
for i in range(len(anchor)):
    answer = max(bfs_longest(anchor[i][0],anchor[i][1]),answer)
print(answer)
### BUGGY CODE ###

N=int(input())
S=input()

Lis=[[] for _ in range(3)]
RGB="RGB"

for i in range(N):
    idx=RGB.index(S[i])
    Lis[idx].append(i+1)

if len(Lis[0])==0 or len(Lis[1])==0 or len(Lis[2])==0:
    print(0)
    exit()

Ng=len(Lis[2])
ans=0
for r in Lis[0]:
    for g in Lis[1]:
        n1=2*r-g
        n2=2*g-r
        n3=(r+g)//2
        Su=Ng
        if n1>0:
            if n1 in Lis[2]:
                Su-=1
        if n2>0:
            if n2 in Lis[2]:
                Su-=1
        if (g-r)%2==0:
            if n3 in Lis[2]:
                Su-=1
        ans+=Su
print(ans)

### FIXED CODE ###

N=int(input())
S=input()

Lis=[[] for _ in range(3)]
RGB="RGB"

for i in range(N):
    idx=RGB.index(S[i])
    Lis[idx].append(i+1)

if len(Lis[0])==0 or len(Lis[1])==0 or len(Lis[2])==0:
    print(0)
    exit()

Ng=len(Lis[2])
ans=0
for r in Lis[0]:
    for g in Lis[1]:
        n1=2*r-g
        n2=2*g-r
        n3=(r+g)//2
        Su=Ng
        if N>=n1>0:
            if S[n1-1]=="B":
                Su-=1
        if N>=n2>0:
            if S[n2-1]=="B":
                Su-=1
        if (g-r)%2==0:
            if S[n3-1]=="B":
                Su-=1
        ans+=Su
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
L = []
for i in range(N):
    l, r = map(int, input().split())
    L.append((r-l+1, l, r+1))
L.sort()


class Bit:
    """
    0-indexed
    # 使用例
    bit = Bit(10)  # 要素数
    bit.add(2, 10)
    print(bit.sum(5))  # 10
    """
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)

    def sum(self, i):
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


class BitImos:
    """
    ・範囲すべての要素に加算
    ・ひとつの値を取得
    の2種類のクエリをO(logn)で処理
    """
    def __init__(self, n):
        self.bit = Bit(n+1)

    def add(self, s, t, x):
        # [s, t)にxを加算
        self.bit.add(s, x)
        self.bit.add(t, -x)

    def get(self, i):
        return self[i]

    def __getitem__(self, key):
        # 位置iの値を取得
        return self.bit.sum(key+1)


imos = BitImos(M+1)
il = 0
a = N
A = [0]*M
for i in range(1, M+1):
    while il<N:
        ra, l, r = L[il]
        if i < ra:
            break
        il+=1
        a-=1
        imos.add(l, r, 1)
    ans = 0
    for j in range(i, M+1, i):
        ans += imos[j]

    A[i-1] = ans + a

print(*A, sep="\n")


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
N, M = map(int, input().split())
L = []
for i in range(N):
    l, r = map(int, input().split())
    L.append((r-l+1, l, r+1))
L.sort()


class Bit:
    """
    0-indexed
    # 使用例
    bit = Bit(10)  # 要素数
    bit.add(2, 10)
    print(bit.sum(5))  # 10
    """
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)

    def sum(self, i):
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


class BitImos:
    """
    ・範囲すべての要素に加算
    ・ひとつの値を取得
    の2種類のクエリをO(logn)で処理
    """
    def __init__(self, n):
        self.bit = Bit(n+1)

    def add(self, s, t, x):
        # [s, t)にxを加算
        self.bit.add(s, x)
        self.bit.add(t, -x)

    def get(self, i):
        return self[i]

    def __getitem__(self, key):
        # 位置iの値を取得
        return self.bit.sum(key+1)


imos = BitImos(M+1)
il = 0
a = N
A = [0]*M
for i in range(1, M+1):
    while il<N:
        ra, l, r = L[il]
        if i < ra:
            break
        il+=1
        a-=1
        imos.add(l, r, 1)
    ans = 0
    for j in range(i, M+1, i):
        ans += imos[j]

    A[i-1] = ans + a

print(*A, sep="\n")
### BUGGY CODE ###

n=int(input())
cnt=0
for i in range(n+1):
  if set(str(i))=={'7','5','3'}:
    cnt +=1
print(cnt)

### FIXED CODE ###

n = int(input())
 
def dfs(s):

    if int(s) > n:
        return 0
    if s.count('3') > 0 and s.count('5') > 0 and s.count('7') > 0:
        cnt = 1
    else:
        cnt = 0
    cnt += dfs(s + '3')
    cnt += dfs(s + '5')
    cnt += dfs(s + '7')
    return cnt
 
 
print(dfs('0'))
### BUGGY CODE ###

N = int(input())

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

P = [0] + P
P_ = [0] * len(P)
     
count = 0
for i in range(1, N+1):
    P_[P[i]] = 1
    if sum(P_[:P[i]]) > 0:
        continue
    count += 1
    if sum(P_[:P[i]]) == P[i]-1:
        break

print(count)

### FIXED CODE ###

N = int(input())

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

P = [0] + P
     
count = 0
min = 10000000000000
for i in range(1, N+1):
    if min > P[i]:
        min = P[i]
    elif min < P[i]:
        continue
    """
    for j in range(1, i+1):
        #print(i, P[i], j , P[j])
        if P[i] > P[j]:
            #print("out", i)
            break
    else:
        #print("ok", i)
        count += 1
    """
    count += 1
        
    if P[i] == 1:
        break

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

def main():
    import functools
    import operator
    n = int(input())
    inlis = list(map(int, input().split()))
    ans = functools.reduce(operator.mul, inlis)
    if ans > 10 ** 18:
        ans = -1
    print(ans)
    
 
 
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    from sys import stdin
    input = stdin.readline
    n = int(input())
    inlis = list(map(int, input().split()))
    if 0 in inlis:
        ans = 0
    else:
        ans = 1
        for i in inlis:
            ans *= i
            #print(ans)
            if ans > 10 ** 18:
                ans = -1
                break
    print(ans)
    
 
 
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import heapq
import math

length_heap = []

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

length_list = list(map(int, input().split()))
for index, l in enumerate(length_list):
    heapq.heappush(length_heap, (-l, 1, index))

for i in range(total_cut):
    longest, cut_n, idx = heapq.heappop(length_heap)
    heapq.heappush(length_heap, (-length_list[idx]/(cut_n+1), (cut_n + 1), idx))

result = -heapq.heappop(length_heap)[0]

print(math.ceil(result))


### FIXED CODE ###

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

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

maxx = 10**9
minx = 0

while (maxx - minx != 1):
    midx = (maxx + minx) // 2
    cut_n = sum([math.ceil(length / midx)-1 for length in log_list])
    if cut_n > K:
        minx = midx
    else:
        maxx = midx


print(maxx)
### BUGGY CODE ###

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

mod=998244353
if d[0]!=0:
    print(0)
    exit()
if 0 in d[1:]:
    print(0)
    exit()

ans=1
from collections import Counter
c=Counter(d)

for i in range(1,max(d)+1):
    if i not in c.keys():
        print(0)
        exit()
    ans*=(c[i-1]**c[i])
    ans%=mod

print(ans)


### FIXED CODE ###

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

mod=998244353
if d[0]!=0:
    print(0)
    exit()
if 0 in d[1:]:
    print(0)
    exit()

ans=1
from collections import Counter
c=Counter(d)

for i in range(1,max(d)+1):
    if not i in c:
        print(0)
        exit()
    ans*=(c[i-1]**c[i])
    ans%=mod

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

import sys
import functools
import itertools
import math
from collections import deque

def bfs(H, W, S):
    visited = [[False]*(W+2) for _ in range(H+2)]
    unvisited = deque([(1,1)])
    dist = 1
    while unvisited:
        dist += 1
        un = deque()
        for x, y in unvisited:
            visited[y][x] = True
            if S[y-1][x] != '#' and visited[y-1][x] == False:
                un.append((x, y-1))

            if S[y+1][x] != '#' and visited[y+1][x] == False:
                if y+1 == H and x == W:
                    return dist
                un.append((x, y+1))

            if S[y][x-1] != '#' and visited[y][x-1] == False:
                un.append((x-1, y))

            if S[y][x+1] != '#' and visited[y][x+1] == False:
                if y == H and x+1 == W:
                    return dist
                un.append((x+1, y))
        unvisited = un

    return -1

def main():
    H, W = map(int, input().split())
    S = ['#'+input()+'#' for _ in range(H)]
    S.insert(0,'#'*(W+2))
    S.append('#'*(W+2))
    step = bfs(H,W,S)
    white = sum([n.count('.') for n in S])
    if step == -1:
        print(step)
    else:
        print(white - step)

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque

def bfs(H, W, S):
    visited = [[False]*(W+2) for _ in range(H+2)]
    visited[1][1] = True
    unvisited = deque([(1,1)])
    dist = 1
    while unvisited:
        dist += 1
        un = deque()
        for x, y in unvisited:
            for t1, t2 in zip([-1,+1,0,0],[0,0,-1,1]):
                dx = x + t1
                dy = y + t2
                if S[dy][dx] != '#' and not visited[dy][dx]:
                    if dy == H and dx == W:
                        return dist
                    un.append((dx,dy))
                    visited[dy][dx] = True
        unvisited = un

    return -1

def main():
    H, W = map(int, input().split())
    S = ['#'+input()+'#' for _ in range(H)]
    S.insert(0,'#'*(W+2))
    S.append('#'*(W+2))
    step = bfs(H,W,S)
    white = sum([n.count('.') for n in S])
    if step == -1:
        print(step)
    else:
        print(white - step)

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

# -*- coding: utf-8 -*-
"""
Created on Sat May  2 19:11:18 2020

@author: Kanaru Sato
"""

n,k = list(map(int, input().split()))
h = list(map(int, input().split()))
dp = [float("inf")]*n

for i in range(n):
    if i == 0:
        dp[i] = 0
    elif i == 1:
        dp[i] = abs(h[1]-h[0])
    else:
        for j in range(1,min(i+1,k+1)):
            dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))

print(dp[n-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat May  2 19:11:18 2020

@author: Kanaru Sato
"""

n,k = list(map(int, input().split()))
h = list(map(int, input().split()))
dp = [float("inf")]*n

for i in range(n):
    if i == 0:
        dp[i] = 0
    elif i == 1:
        dp[i] = abs(h[1]-h[0])
    else:
        for j in range(1,min(i+1,k+1)):
            dp[i] = min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))

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

import math
# def permutations_count(n, r):
#     return math.factorial(n) // math.factorial(n - r)

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N = int(input())

sum = 0
for i in range(2, N+1):
    basyo = combinations_count(N, i)
    # basyo = permutations_count(N, i) / 2  # 9と0が入る場所。i箇所。
    # zerokyuu = i*(i-1)*2(i-2)  # 入る場所に0と9を入れる。
    zerokyuu = 2**i - 2  # 全部0と全部9を抜く。
    iti_hachi = 8**(N-i)  # 残った部分に1-8が入る全通り
    sum += basyo * zerokyuu * iti_hachi

print(int(sum % (10**9+7)))


### FIXED CODE ###

N = int(input())
print((10**N - 9**N - 9**N + 8**N) % (10**9+7))
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
P = [p - 1 for p in P]
C = list(map(int, input().split()))

vis = [False] * N
ans = [-float("inf")] * N

for root in range(N):
  vis[root] = True
  
  cycle = [root]
  costs = [C[root]]
  u = P[root]
  vis[u] = True
  
  while u != root:
    cycle.append(u)
    costs.append(C[u])
    u = P[u]
    vis[u] = True

  L = len(cycle)
  S = sum(costs)
  for i, v in enumerate(cycle):
    cnt = 0
    for step in range(1, min(L, K) + 1):
      cnt += costs[(i + step) % L]
      val1 = cnt
      val2 = cnt + (K - step) // L * S
      ans[v] = max(ans[v], val1, val2)

print(max(ans))

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
P = [p - 1 for p in P]
C = list(map(int, input().split()))

vis = [False] * N
ans = [-float("inf")] * N

for root in range(N):
  if vis[root]:
    continue
  vis[root] = True
  
  cycle = [root]
  costs = [C[root]]
  u = P[root]
  vis[u] = True
  
  while u != root:
    cycle.append(u)
    costs.append(C[u])
    u = P[u]
    vis[u] = True

  L = len(cycle)
  S = sum(costs)
  for i, v in enumerate(cycle):
    cnt = 0
    for step in range(1, min(L, K) + 1):
      cnt += costs[(i + step) % L]
      val1 = cnt
      val2 = cnt + (K - step) // L * S
      ans[v] = max(ans[v], val1, val2)

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

n = int(input())
A = list(map(int, input().split()))
q = int(input())
B,C = [], []

for _ in range(q):
    b, c = list(map(int, input().split()))
    B.append(b)
    C.append(c)


for b, c in zip(B,C):
    ans = 0
    for i, a in enumerate(A):
        if a == b:
            ans += c
            A[i] = c
        else:
            ans += a
    print(ans)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
q = int(input())
B,C = [], []

for _ in range(q):
    b, c = list(map(int, input().split()))
    B.append(b)
    C.append(c)

ans = sum(A)

d = {}
for a in A:
    d.setdefault(a, 0)
    d[a] += 1

for b, c in zip(B,C):
    d.setdefault(b, 0)
    d.setdefault(c, 0)
    ans -= d[c] * c
    ans -= d[b] * b
    d[c] += d[b]
    d[b] = 0
    ans += d[c] * c
    ans += d[b] * b
    print(ans)
### BUGGY CODE ###

def checkRGB(a,b,c):
    if a == b or b == c or c == a:
        return 0
    else:
        return 1

N = int(input())
S = input()

if N<4:
    print(0)
    exit()
sum1 = S.count("R")*S.count("G")*S.count("B")
sum2 = 0
for i in range(1,N):
    center = S[i]
    for j in range(i):
        left = S[j]
        if 2*i-j<N:
            right = S[2*i-j]
            sum2 +=  checkRGB(left,center,right)

print(sum1-sum2)


### FIXED CODE ###

def checkRGB(a,b,c):
    if a == b or b == c or c == a:
        return 0
    else:
        return 1

N = int(input())
S = input()

if N<4:
    print(0)
    exit()
sum1 = S.count("R")*S.count("G")*S.count("B")
sum2 = 0
for i in range(0,N-2):
    left = S[i]
    for j in range(i+1,(N+i)//2+(N+i)%2):
        center = S[j]
        right = S[2*j-i]
        if checkRGB(left,center,right):
            sum2 += 1
print(sum1-sum2)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([xy[0],i])
    b.append([xy[1],i])

a.sort()
b.sort()
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for [x0, j0], [x1, j1]  in zip(a, a[1:]):
    adj[j0].append([x1-x0, j1])
    adj[j1].append([x1-x0, j0])
for [y0, j0], [y1, j1] in zip(b, b[1:]):
    adj[j0].append([y1-y0, j1])
    adj[j1].append([y1-y0, j0])

#print(adj)
    
# Prim's algorithm
d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
totalcost = 0 
while h:
    cost, node = heapq.heappop(h)
    if visited[node] != True and cost < d[node]:
    #if visited[node] != True:        
        d[node] = cost
        visited[node] = True
        totalcost += cost
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]] == True:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(totalcost)
        


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq
import sys
input = sys.stdin.readline

n = int(input())
a = [[] for _ in range(n)]
b = [[] for _ in range(n)]
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a[i]=[xy[0],i]
    b[i]=[xy[1],i]

a.sort()
b.sort()
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for [x0, j0], [x1, j1]  in zip(a, a[1:]):
    adj[j0].append([x1-x0, j1])
    adj[j1].append([x1-x0, j0])
for [y0, j0], [y1, j1] in zip(b, b[1:]):
    adj[j0].append([y1-y0, j1])
    adj[j1].append([y1-y0, j0])

#print(adj)
    
# Prim's algorithm
#d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
totalcost = 0 
while h:
    cost, node = heapq.heappop(h)
    #if visited[node] != True and cost < d[node]:
    if visited[node] != True:        
        #d[node] = cost
        visited[node] = True
        totalcost += cost
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]]:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(totalcost)
### BUGGY CODE ###

n, m = (int(i) for i in input().split()) 
p, y = [], []
yd = [[] for i in range(n+1)]
for i in range(m):
  tmp = [int(i) for i in input().split()]
  p.append(tmp[0])
  y.append(tmp[1])
  yd[p[i]].append(y[i])
for i in range(n):
  yd[i+1].sort()
for i in range(m):
  l = str(p[i])
  r = str(yd[p[i]].index(y[i])+1)
  lzero = l.zfill(6)
  rzero = r.zfill(6)
  print(lzero + rzero)


### FIXED CODE ###

n, m = (int(i) for i in input().split()) 
py = [[int(i) for i in input().split()] for i in range(m)]
cnt = [0]*(n+1)
ids = {}
for p,y in sorted(py, key=lambda x: x[1]):
  cnt[p] += 1
  ids[y] = '%06d%06d' % (p, cnt[p])
for _, y in py:
  print(ids[y])
### BUGGY CODE ###

A,B,C = map(int,input().split())
 
counter = 0
 
while not A == B == C:
    if max([A,B,C])-min([A,B,C]) > 1:
        if A < B and A < C:
            A += 2
        elif B < A and B < C:
            B += 2
        else:
            C += 2
        counter += 1
    else:
        if A < C and B < C:
            A += 1
            B += 1
        elif A < B and C < B:
            A += 1
            C += 1
        else:
            B += 1
            C += 1
        counter += 1
        
print(counter)

### FIXED CODE ###

A,B,C = map(int,input().split())
 
counter = 0
 
while not A == B == C:
    A,B,C = sorted([A,B,C])
    if C - A > 1:
        A += 2
        counter += 1
    else:
        A += 1
        B += 1
        counter += 1
        
print(counter)
### BUGGY CODE ###

import numpy as np
import math
from functools import reduce

# def gcd(*numbers):
#     return reduce(math.gcd, numbers)

# def gcd_list(numbers):
#     return reduce(math.gcd, numbers)

k = int(input())

# ans_array = np.zeros((k, k, k), dtype = np.int)

ans = 0

for i in range(k):
  for j in range(k):
    for h in range(k):
      ans += math.gcd(math.gcd(i+1, j+1), h+1)

# print(ans_array)

# ans = np.sum(ans_array)

print(ans)

### FIXED CODE ###

import math

k = int(input())

ans = 0

for i in range(k):
  for j in range(i,k):
    for h in range(j, k):
      if i == j == h:
        ans += math.gcd(math.gcd(i+1, j+1), h+1)
      elif (i != j) and (j != h) and (i != h):
        ans += math.gcd(math.gcd(i+1, j+1), h+1) * 6
      else:
      	ans += math.gcd(math.gcd(i+1, j+1), h+1) * 3
      
print(ans)
### BUGGY CODE ###

import sys
# input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

S = str(input())
K = int(input())

N = len(S)
lst = []
lst_append = lst.append
s = set()
s_add = s.add
for i in range(N):
    for j in range(i + 1, N + 1):
        if S[i:j] in s:
            continue
        else:
            s.add(S[i:j])
            lst_append(S[i:j])

lst.sort()
print (lst[K - 1])
# print (lst)

### FIXED CODE ###

def main():
    S = str(input())
    K = int(input())
    N = len(S)

    tmp = [[] for _ in range(26)]
    for i in range(N):
        tmp[ord(S[i]) - ord('a')].append(i)

    lst = []
    lst_append = lst.append
    s = set()
    s_add = s.add
    for num in tmp:
        for i in num:
            for j in range(i + 1, min(N, i + K) + 1):
                if S[i:j] in s:
                    continue
                else:
                    s_add(S[i:j])
                    lst_append(S[i:j])
        if len(s) >= K:
            lst.sort()
            print (lst[K - 1])
            # print (lst)
            return

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

n = int(input())
ans = 0
p = [0,0]
now = [0,0]
p[0] = n%10
p[1] = 10 - n%10
n = n//10
ans = min(p[0], p[1] + 1)
for _ in range(10**6+1):
  if n <= 0:break
  now[0] = min(p[0] + n%10, p[1] + n%10 + 1)
  now[1] = min(p[0] + 10 - n%10, p[1] + 9 - n%10)
  ans = min(now[0], now[1] + 1)
  n = n//10
  p[0],p[1] = now[0],now[1]
print(ans)


### FIXED CODE ###

import sys
n = [int(i) for i in sys.stdin.readline().rstrip()[::-1]]
ans = 0
i = 0
p = [n[i],10 - n[i]]
now = [0,0]
i += 1
ans = min(p[0], p[1] + 1)
for i in range(1,len(n)):
  now[0] = min(p[0] + n[i]%10, p[1] + n[i]%10 + 1)
  now[1] = min(p[0] + 10 - n[i]%10, p[1] + 9 - n[i]%10)
  ans = min(now[0], now[1] + 1)
  p[0],p[1] = now[0],now[1]
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for x in range(n)]

import copy

for i in range(n):
   b = copy.deepcopy(a)
   b.pop(i)
   print(max(b))


### FIXED CODE ###

n = int(input())
A = [int(input()) for x in range(n)]

right = [0]
left = [0]

for a in A:
   left.append(max(a, left[-1]))

for a in reversed(A):
   right.append(max(a, right[-1]))

for i in range(n):
   print(max(left[i], right[n-i-1]))
### BUGGY CODE ###

n = int(input())
c = input()
C = [True] * n

for i in range(n):
    if c[i] == 'W':
        C[i] = False
r = C.count(True)

count = 0
while not all(C[:r]):
    a = C.index(False)
    C.reverse()
    b = n-1 - C.index(True)
    C.reverse()
    C[a], C[b] = True, False
    count += 1
print(count)

### FIXED CODE ###

n = int(input())
c = input()

a = c.count('R')
b = c[:a].count('W')
print(b)
### BUGGY CODE ###

s = input()
ans = 0
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        if int(s[i:j])%2019==0:
            ans += 1
print(ans)

### FIXED CODE ###

s = list(input())
mod = 2019
tot = [0]
ans = 0
dp = [0 for _ in range(2020)]
dp[0] = 1
for i in range(len(s)):
    nx = tot[i] + int(s[i])*(pow(10,(len(s)-i),mod))
    nx %= mod
    if dp[nx] != 0:
        ans += dp[nx]
    dp[nx] += 1
    tot.append(nx)
print(ans)