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

from collections import deque
N = int(input())
S = input().strip()
kmax = 0
for k in range(1,N//2+1):
    C = {}
    a = deque(list(S[:k]))
    C[tuple(a)]=[0]
    for i in range(1,N-k+1):
        a.popleft()
        a.append(S[i+k-1])
        if tuple(a) not in C:
            C[tuple(a)] = []
        C[tuple(a)].append(i)
    for a in C:
        if len(C[a])>=2:
            flag = 0
            for i in range(1,len(C[a])):
                if C[a][i]-C[a][i-1]>=k:
                    flag = 1
                    break
            if flag==1:
                kmax = k
                break
print(kmax)

### FIXED CODE ###

N = int(input())
S = input().strip()
cmax = 0
for k in range(1,N):
    X = S[:N-k]
    Y = S[k:]
    cur = 0
    cnt = 0
    for i in range(N-k):
        if X[i]!=Y[i]:
            cmax = max(cmax,min(cnt,k))
            cur = i
            cnt = 0
        else:
            cnt += 1
    cmax = max(cmax,min(cnt,k))
print(cmax)
### BUGGY CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0 for j in range(M+1)]for i in range(N+1)]
for j in range(M+1):
    dp[0][j] = 1
for i in range(N+1):
    dp[i][0] = 1

for i in range(N):
    for j in range(M):
        if S[i] == T[j]:
            dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j])%MOD
        else:
            dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j] - dp[i][j])%MOD

print(dp[N][M])


### FIXED CODE ###

N, M = map(int, input().split())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [[0 for j in range(M+1)]for i in range(N+1)]
for j in range(M+1):
    dp[0][j] = 1
for i in range(N+1):
    dp[i][0] = 1

for i in range(N):
    for j in range(M):
        if S[i] == T[j]:
            dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j])%MOD
        else:
            dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j] - dp[i][j])%MOD

print(dp[N][M])
### BUGGY CODE ###

import sys
n = int(input())
x = list(map(int, sys.stdin.readline().split()))
for i in range(n):
    tmp = x[:i] + x[i+1:]
    tmp.sort()
    print(tmp[n//2-1])

### FIXED CODE ###

import sys
import copy
n = int(input())
x = list(map(int, sys.stdin.readline().split()))
y = sorted(x)
for i in x:
    if y[n//2] > i:
        print(y[n//2])
    else:
        print(y[n//2-1])
### BUGGY CODE ###

n,q = map(int, input().split())
s = input()
lr = [list(map(int,input().split())) for i in range(q)]
for i in range(q):
  print(len(s[lr[i][0]-1:lr[i][1]].replace('AC',':').split(':'))-1)

### FIXED CODE ###

n,q = map(int, input().split())
s = input()
tmp=[0]
l,cnt=0,0
r=2
while r<=n:
  if 'AC' == s[l:r]:
    cnt+=1
    l=r
    tmp.append(cnt)
    tmp.append(cnt)
    r+=2
  else:
    tmp.append(cnt)
    l+=1
    r+=1
for i in range(q):
  l,r = map(int,input().split())
  print(tmp[r-1]-tmp[l-1])
### BUGGY CODE ###

import sys
import math
if sys.version_info.minor >= 5:
    from math import gcd
else:
    from fractions import gcd


def inv(x, mod):
    return pow(x, mod-2, mod)


def lcm(arr, mod = 10 ** 9 + 7):
    ret = 1
    for a in arr:
        ret = ret * a // gcd(ret, a)
    return ret

mod = 10 ** 9 + 7

N = int(input())
A = [int(x) for x in input().split()]
a = lcm(A)
ans = [a // x % mod for x in A]
print(sum(ans) % mod)


### FIXED CODE ###

import sys
import math
if sys.version_info.minor >= 5:
    from math import gcd
else:
    from fractions import gcd


def inv(x, mod):
    return pow(x, mod-2, mod)


def lcm(arr, mod = 10 ** 9 + 7):
    ret = 1
    for a in arr:
        ret = ret * a // gcd(ret, a)
    return ret

mod = 10 ** 9 + 7

N = int(input())
A = [int(x) for x in input().split()]
a = lcm(A)
print(sum(a * inv(x, mod) for x in A) % mod)
### BUGGY CODE ###

N = int(input())

cnt = 0
for i in range(1, N + 1):
    n_str = str(i)

    pre = n_str[0]
    suf = n_str[-1]

    if suf == '0':
        continue

    for j in range(1, N + 1):
        m_str = str(j)

        pre1 = m_str[0]
        suf1 = m_str[-1]

        if suf1 == '0':
            continue

        if pre == suf1 and suf == pre1:
            cnt += 1

print(cnt)

### FIXED CODE ###

from collections import defaultdict

d = defaultdict(int)
N = int(input())

for n in range(1, N + 1):
    n = str(n)

    a = n[0]
    b = n[-1]

    d[(a, b)] += 1


s = 0
for i in range(10):
    for j in range(10):

        s += d[(str(j), str(i))] * d[(str(i), str(j))]

print(s)
### BUGGY CODE ###

N, Q = map(int, input().split(" "))
S = input()
qs = [list(map(int, input().split(" "))) for i in range(Q)]

for q in qs:
    cnt = 0
    target = S[q[0]-1:q[1]]
    for i in range(q[1] - q[0]):
        if target[i:i+2] == "AC":
            cnt += 1
    print(cnt)

### FIXED CODE ###

N, Q = map(int, input().split(" "))
S = input()
ac_cnts = [0]
ac_cnt = 0
for i in range(N-1):
    if S[i:i+2] == "AC":
        ac_cnt += 1
    ac_cnts.append(ac_cnt)
for j in range(Q):
    l, r = map(int, input().split(" "))
    print(ac_cnts[r-1] - ac_cnts[l-1])
### BUGGY CODE ###

n = int(input())
a = input().split()
q = int(input())
b = []
c = []
for i in range(q):
    stdins = input().split()
    b.append(stdins[0])
    c.append(stdins[1])

for i in range(q):
    for j in range(n):
        a[j] = a[j].replace(b[i], c[i])
    ans = sum([int(an) for an in a])
    print(ans)


### FIXED CODE ###

n = int(input())
a = input().split()

a_cnts = {}
a_sum = 0
for an in a:
    if an in a_cnts.keys():
        a_cnts[an] += 1
    else:
        a_cnts[an] = 1
    a_sum += int(an)

q = int(input())

for i in range(q):
    (b, c) = input().split()

    if b in a_cnts.keys():
        hit_cnt = a_cnts[b]
        del a_cnts[b]
        if c in a_cnts.keys():
            a_cnts[c] += hit_cnt
        else:
            a_cnts[c] = hit_cnt
        a_sum += (int(c) - int(b))*hit_cnt

    print(a_sum)
### BUGGY CODE ###

#a,b=map(int,input().split())
import numpy as np

s=input()
n=len(s)
MOD=1000000007
wayA=np.array([0,0,0,0],dtype=np.int64)
wayB=np.array([0,0,0,0],dtype=np.int64)
wayC=np.array([0,0,0,0],dtype=np.int64)
MOD2=np.array([MOD,MOD,MOD,MOD],dtype=np.int64)
hatena=0
for c in s:
	if c=="A":
		wayA[0]+=1
	if c=="B":
		wayB+=wayA
	if c=='C':
		wayC+=wayB
	if c=='?':
		wayC+=np.roll(wayB,1)
		wayB+=np.roll(wayA,1)
		wayA[1]+=1
		hatena+=1
	wayA%=MOD2
	wayB%=MOD2
	wayC%=MOD2
ans=0
for i in range(0,4):
	p3=1
	for j in range(hatena-i):
		p3*=3
		p3%=MOD
	ans+=p3*wayC[i]
	ans=ans%MOD
print(int(ans))

### FIXED CODE ###

#a,b=map(int,input().split())
import numpy as np

s=input()
n=len(s)
wayA=np.array([0,0,0,0],dtype=np.int64)
wayB=np.array([0,0,0,0],dtype=np.int64)
wayC=np.array([0,0,0,0],dtype=np.int64)
hatena=0
MOD=1000000007
for c in s:
	if c=="A":
		wayA[0]=wayA[0]+1
	if c=="B":
		wayB+=wayA;
	if c=='C':
		wayC=wayC+wayB
	if c=='?':
		wayC[1]=wayC[1]+wayB[0]
		wayC[2]=wayC[2]+wayB[1]
		wayC[3]=wayC[3]+wayB[2]
		wayB[1]=wayB[1]+wayA[0]
		wayB[2]=wayB[2]+wayA[1]
		wayA[1]=wayA[1]+1
		hatena=hatena+1
	for z in range(0,4):
		wayA[z]=wayA[z]%MOD
		wayB[z]=wayB[z]%MOD
		wayC[z]=wayC[z]%MOD
ans=0
for i in range(0,4):
	p3=1
	if wayC[i]<=0:
		continue
	for k in range(0,hatena-i):
		p3=p3*3
		p3=p3%MOD
	ans=ans+p3*wayC[i]
	ans=ans%MOD
print(int(ans))
### BUGGY CODE ###

S = input()
Q = int(input())
Ss = S
for i in range(Q) :
    Query = input()
    q = Query.split(" ")
    if int(q[0]) == 1 :
        Ss = Ss[::-1]
    else:
        if int(q[1]) == 1 :
            Ss = str(q[2]) + Ss
        else:
            Ss = Ss + str(q[2])
print(Ss)

### FIXED CODE ###

S = input()
Q = int(input())
flip = 0
head = []
tail = []
for i in range(Q):
  Query = input().split()
  if len(Query) == 3:
    T,F,C = Query
    F = int(F)-1
    if F^flip == 1:
      tail.append(C)
    else:
      head.append(C)
  else:
    flip ^= 1
if flip:
  head, tail = tail, head
  S = S[::-1]
head = ''.join(head[::-1])
tail = ''.join(tail)
print(head+S+tail)
### BUGGY CODE ###

s,c = map(int,input().split(" "))



counter = 0


while True:
    #print("counter:",counter)
    #print("s:",s)
    #print("c:",c)
    
    if c >= 2 and s >= 1:
        s -= 1
        c -= 2
        counter += 1
    if s == 0 and c >= 2:
        c -= 2
        s += 1
    if c <= 1:
        break


print(counter)




### FIXED CODE ###


n,m=map(int,input().split())
first=min(n,m//2)
n -=first
m-=first*2
second = m//4
print(second+first)
### BUGGY CODE ###

MAX_PRIME = 10**5
is_prime = [1] * MAX_PRIME
primes = []
is_prime[0] = 0
is_prime[1] = 0
for i in range(MAX_PRIME):
    if is_prime[i]:
        primes.append(i)
        for j in range(2, ((MAX_PRIME-1)//i) + 1):
            is_prime[i*j] = 0

def factorization(n):
    factor = {}
    for p in primes:
        if p ** 2 > n:
            break
        while n % p == 0:
            n //= p
            if p not in factor:
                factor[p] = 1
            else:
                factor[p] += 1
    if n > 1:
        factor[n] = 1
    return factor

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

ans = 0
l = {}
law = 10 ** 9 + 7
for x in a:
    fx = factorization(x)
    for p, c in fx.items():
        if p not in l:
            l[p] = c
            ans *= p ** c
            ans %= law
        elif c > l[p]:
            ans *= p ** (c - l[p])
            ans %= law
            l[p] = c
    b = 1
    for p, c in l.items():
        if p in fx:
            b *= p ** (l[p] - fx[p])
        else:
            b *= p ** l[p]
        b %= law
    ans += b
    ans %= law
print(ans)

### FIXED CODE ###

MAX_PRIME = 10**3
is_prime = [1] * MAX_PRIME
primes = []
is_prime[0] = 0
is_prime[1] = 0
for i in range(MAX_PRIME):
    if is_prime[i]:
        primes.append(i)
        for j in range(2, ((MAX_PRIME-1)//i) + 1):
            is_prime[i*j] = 0

def factorization(n):
    factor = {}
    for p in primes:
        if p ** 2 > n:
            break
        while n % p == 0:
            n //= p
            if p not in factor:
                factor[p] = 1
            else:
                factor[p] += 1
    if n > 1:
        factor[n] = 1
    return factor
def extGCD(a, b):
    if b == 0:
        return a, 1, 0
    g, y, x = extGCD(b, a%b)
    y -= a//b * x
    return g, x, y
def moddiv(a, b):
    _, inv, _ = extGCD(b, law)
    return a * inv % law

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

ans = 0
l = {}
lmod = 1
law = 10 ** 9 + 7
for x in a:
    fx = factorization(x)
    for p, c in fx.items():
        if p not in l:
            ans *= p ** c
            lmod *= p ** c
            ans %= law
            lmod %= law
            l[p] = c
        elif c > l[p]:
            ans *= p ** (c - l[p])
            lmod *= p ** (c - l[p])
            ans %= law
            lmod %= law
            l[p] = c
    b = moddiv(lmod, x)
    ans += b
    ans %= law
print(ans)
### BUGGY CODE ###

*a, = map(int, open(0).read().split())
b = a[1]
c = 1
l = []
while True:
    if b in l:
        print(-1)
        exit()
    elif b == 2:
        print(c)
        exit()
    l += [b]
    c += 1
    b = a[b]

### FIXED CODE ###

*a, = map(int, open(0).read().split())
b = a[1]
l = []
for i in range(a[0]):
    if b == 2:
        print(i+1)
        exit()
    b = a[b]
print(-1)
### BUGGY CODE ###

a = int(input())
ar = list(map(int,input().split(" ")))
br = set(ar)
cr = []
for r in br:
    if ar.count(r) >= 2:
        if ar.count(r) % 2 == 1:
            for i in range(ar.count(r) - 1):
                cr.append(r)
        else:
            for i in range(ar.count(r)):
                cr.append(r)
cr = sorted(cr,reverse=True)
if len(cr) < 4:
    print(0)
else:
    print(cr[0] * cr[2])

### FIXED CODE ###

import collections
a = int(input())
ar = list(map(int,input().split(" ")))
br = collections.Counter(ar)
cr = []
for k,v in br.items():
    if v >= 4:
        cr.append(k)
        cr.append(k)
    elif v >= 2:
        cr.append(k)
cr = sorted(cr,reverse=True)
if len(cr) < 2:
    print(0)
else:
    print(cr[0] * cr[1])
### BUGGY CODE ###

N, A, B = map(int, input().split())
if A == 0:
    print('0')
elif B == 0:
    print(N)
else:
    result = 0
    while N > 0:
        if N - A > 0:
            result += A
        else:
            result += N
        N -= (A + B)
    print(result)

### FIXED CODE ###

N, A, B = map(int, input().split())
if A == 0:
    print('0')
elif B == 0:
    print(N)
else:
    tmp = N // (A + B)
    result = tmp * A
    N -= tmp * (A + B)
    if N > A:
        result += A
    else:
        result += N
    print(result)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

r, c, k = map(int, input().split())
vals = [[0]*c for _ in range(r)]
for _ in range(k):
    x, y, v = map(int, input().split())
    vals[x-1][y-1] = v
dp = [[[0]*4 for j in range(c)] for i in range(r)]
for i in range(r):
    for j in range(c):
        if i > 0:
            tmp = 0
            for k in range(4):
                if tmp < dp[i-1][j][k]:
                    tmp = dp[i-1][j][k]
            dp[i][j][0] = tmp
        if j > 0:
            for k in range(4):
                if dp[i][j][k] < dp[i][j-1][k]:
                    dp[i][j][k] = dp[i][j-1][k]
        for k in range(3, 0, -1):
            if dp[i][j][k] < dp[i][j][k-1] + vals[i][j]:
                dp[i][j][k] = dp[i][j][k-1] + vals[i][j]
print(max(dp[r-1][c-1]))

### FIXED CODE ###

from sys import stdin
input = stdin.readline

r, c, k = map(int, input().split())
vals = [[0]*c for _ in range(r)]
for _ in range(k):
    x, y, v = map(int, input().split())
    vals[x-1][y-1] = v
dp = [[0]*4 for j in range(c)]
for j in range(c):
    if j > 0:
        for k in range(4):
            dp[j][k] = dp[j-1][k]
    if vals[0][j] > 0:
        for k in reversed(range(3)):
            if dp[j][k+1] < dp[j][k] + vals[0][j]:
                dp[j][k+1] = dp[j][k] + vals[0][j]
for i in range(1, r):
    tmp = [[max(dp[j]), 0, 0, 0] for j in range(c)]
    for j in range(c):
        if j > 0:
            for k in range(4):
                if tmp[j][k] < tmp[j-1][k]:
                    tmp[j][k] = tmp[j-1][k]
        if vals[i][j] > 0:
            for k in reversed(range(3)):
                if tmp[j][k+1] < tmp[j][k] + vals[i][j]:
                    tmp[j][k+1] = tmp[j][k] + vals[i][j]
    dp = tmp
print(max(dp[-1]))
### BUGGY CODE ###

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

a = [[[0 for _ in range(10)] for _ in range(10)] for _ in range(10)]

s = list(S)
lens = len(s)
for i in range(lens):
    ni = int(s[i])
    for j in range(i+1, lens):
        nj = int(s[j])
        for k in range(j+1, lens):
            nk = int(s[k])
            a[ni][nj][nk] = 1

ans = sum(sum(a, []), [])
print(sum(ans))

### FIXED CODE ###

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

a = []
for i in range(10):
    for j in range(10):
        for z in range(10):
            a.append([i,j,z])

s = list(S)
s = [int(i) for i in s]
ans = 0
for n in a:
    flag = 0
    for i,name in enumerate(s):
        if name == n[0]:
            n = n[1:]
            flag += 1
        if flag == 3:
            ans += 1
            break

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

import fractions as f 
a=int(input())
ans=0
for i in range(1,a+1):
 for j in range(1,a+1):
  for k in range(1,a+1):
   ans+=f.gcd(f.gcd(i,j),k)
print(ans)


### FIXED CODE ###

import math as f 
a=int(input())
ans=0
for i in range(1,a+1):
 for j in range(1,a+1):
  for k in range(1,a+1):
   b=f.gcd(i,j)
   ans+=f.gcd(b,k)
print(ans)
### BUGGY CODE ###

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    A = list(map(int, input().split()))

    DP = [[[0] * 3 for _ in range(S + 1)] for _ in range(N + 1)]
    DP[0][0][0] = 1

    for i in range(N):
        DP[i + 1][0][0] = DP[i][0][0] 
        DP[i + 1][0][1] = DP[i][0][0] + DP[i][0][1]
        a = A[i]
        if a > S:
            for j in range(1, S + 1):
                DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1]) % MOD #以前から合計jになっている場合のみOK
        else:
            for j in range(1, a):
                DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1]) % MOD #以前から合計jになっている場合のみOK
            for j in range(a, S + 1):
                DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1] + DP[i][j - a][0] + DP[i][j - a][1]) % MOD

        DP[i + 1][S][2] = (DP[i][S][1] + DP[i][S][2]) % MOD
        if a <= S:
            DP[i + 1][S][2] += DP[i][S - a][0] + DP[i][S - a][1]
        DP[i + 1][S][2] %= MOD

    print (DP[N][S][2])

    # for i in range(N + 1):
    #     print (DP[i])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    A = tuple(map(int, input().split()))

    DP0 = [[0] * (S + 1) for _ in range(N + 1)]
    DP1 = [[0] * (S + 1) for _ in range(N + 1)]
    DP2 = [[0] * (S + 1) for _ in range(N + 1)]

    DP0[0][0] = 1

    for i in range(N):
        DP0[i + 1][0] = DP0[i][0] 
        DP1[i + 1][0] = DP0[i][0] + DP1[i][0]
        a = A[i]
        if a > S:
            for j in range(1, S + 1):
                DP1[i + 1][j] = DP1[i][j] #以前から合計jになっている場合のみOK
        else:
            for j in range(1, a):
                DP1[i + 1][j] = DP1[i][j] #以前から合計jになっている場合のみOK
            for j in range(a, S + 1):
                DP1[i + 1][j] = (DP1[i][j] + DP0[i][j - a] + DP1[i][j - a]) % MOD
                # DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1] + DP[i + 1][j - a][1]) % MOD

        DP2[i + 1][S] = (DP1[i][S] + DP2[i][S])
        if a <= S:
            DP2[i + 1][S] += DP0[i][S - a] + DP1[i][S - a]
        DP2[i + 1][S] %= MOD

    print (DP2[N][S])

    # for i in range(N + 1):
    #     print (DP[i])

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

a, b, c, d = map(int, input().split())
m=0
for i in range(a,b+1):
    if i%c == 0:
        continue
    elif i % d == 0:
        continue
    else:
        m += 1
print(m)

### FIXED CODE ###

from fractions import gcd
a, b, c, d = map(int, input().split())

e = (c*d)//gcd(c,d)

def calc(x):
    return x - (x//c)-(x//d)+(x//e)

print(calc(b)-calc(a-1))
### BUGGY CODE ###

import numpy as np
words = lambda t : list(map(t, input().split()))



h,w = words(int)
wq = [0] * w

grid = []
for i in range(h):
    grid.append(list(input()))

ans = 0
for i in range(h):
    j = 0
    while j < w:
        #print(i,j, grid[i][j])
        if grid[i][j] == '#':
            wq[j] = 0
            j+=1
            continue
        k = 0
        while j+k < w:
            if grid[i][j+k] == '.':
                k += 1
            else:
                break
        #print("k:", k)
        for x in range(j,j+k):
            vplus = 0
            if not wq[x] == 0:
                vplus = wq[x]
            else:
                for vi in range(i-1,-1,-1):
                    if grid[vi][x] == '#':
                        break
                    else:
                        vplus += 1
                for vi in range(i+1,h):
                    if grid[vi][x] == '#':
                        break
                    else:
                        vplus += 1
            ans = max(ans, vplus+k)
            wq[x] = vplus
        j = j+k
print(ans)


### FIXED CODE ###

#import numpy as np
words = lambda t : list(map(t, input().split()))



h,w = words(int)
wq = [0] * w

grid = []
for i in range(h):
    grid.append(list(input()))

ans = 0
for i in range(h):
    j = 0
    while j < w:
        #print(i,j, grid[i][j])
        if grid[i][j] == '#':
            wq[j] = 0
            j+=1
            continue
        k = 0
        while j+k < w:
            if grid[i][j+k] == '.':
                k += 1
            else:
                break
        #print(i,j,k)
        if k + h > ans:
            for x in range(j,j+k):
                vplus = 0
                if not wq[x] == 0:
                    vplus = wq[x]
                else:
                    for vi in range(i-1,-1,-1):
                        if grid[vi][x] == '#':
                            break
                        else:
                            vplus += 1
                    for vi in range(i+1,h):
                        if grid[vi][x] == '#':
                            break
                        else:
                            vplus += 1
                ans = max(ans, vplus+k)
                wq[x] = vplus
        j += k
print(ans)
### BUGGY CODE ###

from collections import defaultdict
n = int(input())
s = input()

dp = [defaultdict(int), defaultdict(int)]

dp[0][""] = 1
for i in range(n):
    for j in dp[i % 2]:
        dp[(i + 1) % 2][j] = dp[i % 2][j]

    for j in dp[i % 2]:
        if len(j) < 3:
            dp[(i + 1) % 2][j + s[i]] += dp[i % 2][j]

ans = 0
for j in dp[n % 2]:
    if len(j) == 3:
        # print(j)
        ans += 1

print(ans)


### FIXED CODE ###

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

dp = [set(), set()]

dp[0].add("")
for i in range(n):
    dp[(i + 1) % 2] = dp[i % 2].copy()
    i1 = (i + 1) % 2
    i0 = (i + 0) % 2
    for j in dp[i0]:
        if len(j) < 3:
            dp[i1].add(j + s[i])

ans = 0
for j in dp[n % 2]:
    if len(j) == 3:
        # print(j)
        ans += 1

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

n = int(input())
list = []
ans = 0
for i in range(n):
  list.append(input())
  list[i] = ''.join(sorted(list[i]))
for i in range(n):
  for j in range(i+1,n):
    if list[i] == list[j]:
      ans += 1
print(ans)


### FIXED CODE ###

n = int(input())
dict= {}
ans = 0
for i in range(n):
  temp = ''.join(sorted(input()))
  if temp in dict:
    dict[temp] += 1
    ans += dict[temp]
  else:
    dict.update([(temp, 0)])
print(ans)
### BUGGY CODE ###

A, B, N = map(int, input().split())
ans = 0

for i in range(min(N+1, B)):
    p = A * i // B
    q = i // B * A
    ans = max(ans, p - q)

print(ans)

### FIXED CODE ###

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

x = min(N, B-1)
p = A * x // B
q = x // B * A
ans = p - q

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

H,W=map(int,input().split())
S=[]
for _ in range(H):
    S.append(input())

from itertools import product

P={}
for i,j in product(range(H),range(W)):
    s=S[i][j]
    path=[]
    for p in [-1,1]:
        if 0<=i+p<H:
            if S[i+p][j]!=s:
                path.append((i+p,j))
        if 0<=j+p<W:
            if S[i][j+p]!=s:
                path.append((i,j+p))
    P[(i,j)]=path
ans=0
for i,j in product(range(H),range(W)):
    path=[(i,j)]
    if S[i][j]=='#':
        que=P[(i,j)]
        path+=que
        ans+=len(que)
    else:
        que=[]
    while len(que)>0:
        tmp=[]
        for q in que:
            for p in P[q]:
                if p not in path:
                    path.append(p)
                    tmp.append(p)
                    if S[p[0]][p[1]]=='.':
                        ans+=1
        que=tmp

print(ans)



### FIXED CODE ###

H,W=map(int,input().split())
S=[]
for _ in range(H):
    S.append(input())

def path(i,j):
    p=[]
    for k in [1,-1]:
        if 0<=i+k<H:
            if S[i][j]!=S[i+k][j]:
                p.append((i+k,j))
        if 0<=j+k<W:
            if S[i][j]!=S[i][j+k]:
                p.append((i,j+k))
    return p
f = [[0 for i in range(W)] for j in range(H)]
ans=0

for i in range(H):
    for j in range(W):
        if f[i][j]==0:
            f[i][j]=1
            b=0
            w=0
            if S[i][j]=='#':
                b+=1
            else:
                w+=1
            que=path(i,j)

            while len(que)>0:
                tmp=[]
                for q in que:
                    q0,q1=q
                    if f[q0][q1]==0:
                        f[q0][q1]=1
                        if S[q0][q1]=='#':
                            b+=1
                        else:
                            w+=1
                        for p in path(q0,q1):
                            if f[p[0]][p[1]]==0:
                                tmp.append(p)
                que=tmp
            ans+=b*w
print(ans)
### BUGGY CODE ###

from heapq import heapify,heappush,heappop

s=input()
K=int(input())
N=len(s)
tmp=[]
heapify(tmp)

for i in range(N):
  for j in range(i,N):
    if len(s[i:j+1])<=K:
      heappush(tmp,s[i:j+1])
  
i=0
zumi=set()
while True:
  s=heappop(tmp)
  if s not in zumi:
    zumi.add(s)
    i += 1
    if i==K:
      print(s)
      exit()



#lis=sorted(tmp)
#print(lis)
#print(lis[K-1])

### FIXED CODE ###

s=input()
K=int(input())
N=len(s)
tmp=set()

for i in range(N):
  for j in range(K):
    t= s[i:i+j+1]
    #print(i,j,t)
    tmp.add(t)
    
lis=sorted(tmp)
#print(lis)
print(lis[K-1])