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

n,q=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n-1)]
px=[list(map(int,input().split())) for i in range(q)]

temp=[[i+1] for i in range(n)]
for i in range(n-2,-1,-1):
    if len(temp[ab[i][1]-1]) >= 2:
        temp[ab[i][0]-1].extend(temp[ab[i][1]-1])
    else:
        temp[ab[i][0]-1].append(ab[i][1]) 


ans=[0 for i in range(n)]
for j in range(q):
    for _ in temp[px[j][0]-1]:
        ans[_-1]+=px[j][1]

print(" ".join(map(str,ans)))

### FIXED CODE ###

n,q=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n-1)]
px=[list(map(int,input().split())) for i in range(q)]

parent=[0 for i in range(n)]
for i in range(n-1):
    parent[ab[i][1]-1]=ab[i][0]
ans=[0 for i in range(n)]
for i in range(q):
    ans[px[i][0]-1]+=px[i][1]
for i in range(1,n):
    if parent[i] != 0:
        ans[i]+=ans[parent[i]-1]


print(" ".join(map(str,ans)))
### BUGGY CODE ###

n = int(input())
s = [""] * n
t = []
for i in range(n):
    s[i] = input()
for i in range(n):
    if s[i] not in t:
        t.append(s[i])
print(len(t))


### FIXED CODE ###

n = int(input())
s = [""] * n
for i in range(n):
    s[i] = input()
s = set(s)
print(len(s))
### BUGGY CODE ###

import sys
N, K = list(map(int,input().split()))
h = list(map(int, input().split()))

score = [sys.maxsize for i in range(N)]

score[0] = 0
score[1] = score[0] + abs(h[1]-h[0])
for i in range(2, N):
    for j in range(max(i-K, 0), i):
        score[i] = min(score[i], score[j] + abs(h[i]-h[j]))

print(score[-1])


### FIXED CODE ###

import sys
N, K = list(map(int,input().split()))
h = list(map(int, input().split()))

score = [sys.maxsize for i in range(N)]

score[0] = 0
score[1] = score[0] + abs(h[1]-h[0])
for i in range(2, N):
    for j in range(max(i-K, 0), i):
        score[i] = min(score[i], score[j] + abs(h[i]-h[j]))

print(score[-1])
### BUGGY CODE ###

n_list = list(input())
n_len_o = len(n_list)
#print(n_list)

while(1):
  flag = "ng"
  n_len = len(n_list)
  for i in range(n_len-1):
    if n_list[i] != n_list[i+1]:
      n_list.pop(i)
      n_list.pop(i)
      flag = "ok"
      break
  if flag == "ng":
    break
#print(n_list)
print(n_len_o-len(n_list))

### FIXED CODE ###

n_list = list(input())
n_len_o = len(n_list)
a = 0
while(1):
  flag = "ng"
  n_len = len(n_list)
  for i in range(a,n_len-1):
    if n_list[i] != n_list[i+1]:
      n_list.pop(i)
      n_list.pop(i)
      if i != 0:
        a = i - 1
      else:
        a = 0
      flag = "ok"
      break
  if flag == "ng":
    break
print(n_len_o-len(n_list))
### BUGGY CODE ###

import heapq as hq
n, m = map(int, input().split())
a = list(map(int, input().split()))
def heapSort(i):
    h = []
    for v in i:
        hq.heappush(h, v)
    return [hq.heappop(h) for i in range(len(h))]
for i in range(m):
    a = heapSort(a)
    a[n-1] //= 2
print(sum(a))

### FIXED CODE ###

import heapq as hq
n, m = map(int, input().split())
a = [-int(i) for i in input().split()]
hq.heapify(a)
for i in range(m):
    minprice = hq.heappop(a)
    hq.heappush(a, (-minprice // 2) * -1)
print(-sum(a))
### BUGGY CODE ###

import numpy as np
import copy

def main():
    N, W= map(int, raw_input().split())
    dp = np.zeros(W+1)
 
    for i in range(N):
        w, v = map(int, raw_input().split())
        dp_temp = copy.deepcopy(dp)
        for j in range(W+1):
            dp_pre = dp[j]
            if j-w > -1:
                dp_update = dp[j-w] + v
            else:
                dp_update = 0
            dp_temp[j] = max(dp_pre, dp_update)
 
        dp = dp_temp
 
    print int(dp[-1])

main()

### FIXED CODE ###

def main():

    N, W = map(int, raw_input().split())
    dp = [0]*(W+1)
 
    for i in xrange(N):
        w, v = map(int, raw_input().split())
        for j in xrange(W, w-1, -1):
            x = dp[j-w] + v
            if x > dp[j]:
                dp[j] = x
 
    print dp[-1]

main()
### BUGGY CODE ###

import collections
N=int(input())
a=[]
A=list(map(int,input().split()))
a=A
c=collections.Counter(a)
d=c.most_common()
for i in range(N):
    ans=0
    for j in range(len(d)):
        if d[j][0]==A[i]:
            ans+=(d[j][1]-1)*(d[j][1]-2)//2
        else:
            ans+=d[j][1]*(d[j][1]-1)//2
    print(ans)

### FIXED CODE ###

import collections
N=int(input())
A=list(map(int,input().split()))
c=collections.Counter(A)
ans=0
for i in c:
    ans+=c[i]*(c[i]-1)//2
for i in range(N):
    a=A[i]
    Ans=ans-c[a]+1
    print(Ans)
### BUGGY CODE ###

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

ans = 0
for i in range(0,k+1):
  for j in range(0,k+1):
    for k in range(0,k+1):
      if(i + j + k == s):
        ans += 1
print(ans)

### FIXED CODE ###

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

ans = 0
if(s == 0):
  print(1)
  exit()
elif(s == 3*k):
  print(1)
  exit()
  
for i in range(0,k+1):
  for j in range(0,k+1):
    z = s - i - j
    if(z >= 0 and z <= k):
      ans += 1
        
print(ans)
### BUGGY CODE ###

MOD = pow(10, 9) + 7

n, k = map(int, input().split())
A = sorted(map(int, input().split()))
B = A[::-1]
fact = [1]
for i in range(1,n+1):
    fact.append((fact[i-1]*i)%MOD)

ans = 0
for i, a in enumerate(A):
    now = k-2
    while now <= n-2-i:
        tmp = ((fact[now] % MOD * pow(fact[now-(k-2)], MOD-2, MOD)) % MOD * pow(fact[k-2], MOD-2, MOD)) % MOD
        ans = (ans - a*tmp)%MOD
        now += 1

for i, b in enumerate(B):
    now = k-2
    while now <= n-2-i:
        tmp = ((fact[now] % MOD * pow(fact[now-(k-2)], MOD-2, MOD)) % MOD * pow(fact[k-2], MOD-2, MOD)) % MOD
        ans = (ans + b*tmp)%MOD
        now += 1
print(ans)


### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline

    MOD = pow(10, 9) + 7

    n, k = map(int, input().split())
    A = sorted(map(int, input().split()))
    B = A[::-1]
    fact = [1]
    for i in range(1, n+1):
        fact.append((fact[i-1]*i)%MOD)
    now = k-2
    S = []
    while now <= n-2:
        tmp = ((fact[now] % MOD * pow(fact[now-(k-2)], MOD-2, MOD)) % MOD * pow(fact[k-2], MOD-2, MOD)) % MOD
        S.append(tmp)
        now += 1
    cumsum = [0, ]
    for i, s in enumerate(S):
        cumsum.append((cumsum[i]+s) % MOD)
    ans = 0
    for i, a in enumerate(A):
        ans = (ans - a*cumsum[-(i+1)])%MOD
        if cumsum[-(i+1)] == 0:
            break
    for i, b in enumerate(B):
        ans = (ans + b*cumsum[-(i+1)])%MOD
        if cumsum[-(i+1)] == 0:
            break
    print(ans)


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

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

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]

mod = 10**9+7

dp = [0] * (n+1)
dp[0] = 1
if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1

for i in range(2, n+1):
    if i not in a:
        temp = dp[i-1] + dp[i-2]
        dp[i] = temp%mod
    else:
        dp[i] = 0

#print(dp)
print(dp[-1])


### FIXED CODE ###

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

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

stairs = [i for i in range(1, n+1)]
a = [0 for _ in range(m)]
for i in range(m):
  a[i] = int(input())
a = set(a)
  
mod = 10**9+7
dp = [0] * (n+1)
dp[0] = 1

#print(test_a)
for i in range(1, n+1):
    if i in a:
        continue
    dp[i] = dp[i] + dp[i-1]
    if i > 1:
        dp[i] = dp[i] + dp[i-2]

#print(dp)
print(dp[-1]%mod)
### BUGGY CODE ###

N,K= map(int,input().split())
health = list(map(int,input().split()))
health = sorted(health,reverse=True)

if K > N: 
    print(0)
else:
    for i in range(K):
        health.pop(0)
    res = sum(health)
    print(res)

### FIXED CODE ###


N, K = map(int, input().split())
Hs = map(int,input().split())
print(sum(sorted(Hs, reverse=True)[K::]))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 整数の入力


def main():
    # a, b
    n = int(input())
    s = []
    for _ in range(n):
        s.append(input())
    print(process(n, s))


def process(n, s):
    count = 0
    for i in range(0, n):
        for k in range(i, n):
            if i == k:
                continue
            if anagram(s[i], s[k]) == True:
                count += 1
    return count


# def anagram(a, b):
#     for i in a:
#         if i in b:
#             b = b.replace(i, '')
#             continue
#         else:
#             return False
#     return True

def anagram(a, b):
    return sorted(a) == sorted(b)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
# 整数の入力


def main():
    # a, b
    n = int(input())
    s = []
    for _ in range(n):
        s.append(input())
    print(process(n, s))


def process(n, s):
    s = list(map(lambda s: ''.join(sorted(s)), s))
    hash = {}

    count = 0
    for i in range(0, n):
        if s[i] in hash:
            hash[s[i]] += 1
        else:
            hash[s[i]] = 1
        count += hash[s[i]] - 1
    return count


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

import collections
import copy
N = int(input())
A = list(map(int,input().split()))
AA = collections.Counter(A)

for i in range(N):
    ans = 0
    AAA = copy.copy(AA)
    AAA[A[i]] -= 1
    for j in AAA.values():
        if j>=2:
            ans += int(j*(j-1)/2)
    print(ans)

### FIXED CODE ###

import collections
import copy
N = int(input())
A = list(map(int,input().split()))
AA = collections.Counter(A)
ans = sum([i*(i-1)//2 for i in AA.values()])

for i in range(N):
    num = ans
    num -= AA[A[i]]-1
    print(num)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
ans = 0
sum_n = [0]*n
for i in range(n):
    sum_n[i] = sum(l[i+1:n]) 
for i in range(n):
    ans += ((l[i]*sum_n[i])%1000000007)
print(ans%1000000007)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
ans = 0
sum_n = [0]*n
sum_n[0] = l[0]
sumall = sum(l)
for i in range(1,n):
    sum_n[i] = sum_n[i-1] + l[i]
for i in range(n):
    ans += ((l[i]*(sumall-sum_n[i]))%1000000007)
print(ans%1000000007)
### BUGGY CODE ###

import math


def comb(n, r):
    mf = math.factorial
    return mf(n) // (mf(n - r) * mf(r))


n = int(input())
c = [''.join(sorted(list(input()))) for _ in range(n)]
s = set(c)

anagram = [0] * len(s)
for i, si in enumerate(s):
    anagram[i] = c.count(si)

print(sum(comb(a, 2) for a in anagram if a > 1))

### FIXED CODE ###

import math
import collections


def comb(n, r):
    mf = math.factorial
    return mf(n) // (mf(n - r) * mf(r))


n = int(input())
s = [''.join(sorted(list(input()))) for _ in range(n)]
c = collections.Counter(s)
print(sum(comb(a, 2) for a in c.values() if a > 1))
### BUGGY CODE ###

N=int(input())
L=[]
for i in range(N):
    L.append(int(input()))

for i in range(N):
    L_temp=L.copy()
    L_temp_p=L_temp.pop(i)
    print(max(L_temp))

### FIXED CODE ###

N=int(input())
L=[]
for i in range(N):
    L.append(int(input()))

L_max=max(L)

L_max_count=0
for l in L:
    if l==L_max:
        L_max_count+=1
    if L_max_count > 1:
        break

for i in range(N):
    now=L[i]
    
    if L_max_count > 1:
        ans=L_max
    
    elif now!=L_max:
        ans=L_max
        
    else:
        L_temp=L.copy()
        L_temp_p=L_temp.pop(i)
        ans=max(L_temp)
    
    print(ans)
### BUGGY CODE ###

from itertools import product

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

cnt = 0
for num in product(range(10), repeat=3):
    i = 0
    for e in s:
        if str(num[i]) == e:
            i += 1
        if i == 3:
            break

    if i == 3:
        cnt += 1

print(cnt)


### FIXED CODE ###

from itertools import product

n = int(input())
s = input()
nums = [str(i) for i in range(10)]

cnt = 0
for num in product(nums, repeat=3):
    i = 0
    for e in s:
        if num[i] == e:
            i += 1
        if i == 3:
            break

    if i == 3:
        cnt += 1

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

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

class HashTable(list):
    def __init__(self, length):
        list.__init__(self)
        self.length = length
        self[:] = [None] * length

    def h1(self, key):
        return key % self.length

    def h2(self, key):
        return 1 + (key % (self.length - 1))

    def h(self, key, i):
        return (self.h1(key) + i*self.h2(key)) % self.length

    def insert(self, key):
        i = 0
        while True:
            j = self.h(key, i)
            if self[j] is None:
                self[j] = key
                return j
            else:
                i += 1
    
    def search(self, key):
        i = 0
        while True:
            j = self.h(key, i)
            if self[j] == key:
                return j
            elif self[j] is None or i >= self.length:
                return None
            else:
                i += 1

def getNum(char):
    char2num = str.maketrans("ACGT", "1234")
    return int(char.translate(char2num), 5)

if __name__ == '__main__':

    n = int(input())
    T = HashTable(1046527)
    C = [input().split(" ") for i in range(n)]
    
    for command, char in C:
        num = getNum(char)
        if command[0] == "i":
            T.insert(num)
        else:
            if T.search(num) is None:
                print("no")
            else:
                print("yes")



### FIXED CODE ###

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

class HashTable(list):
    def __init__(self, length):
        list.__init__(self)
        self.length = length
        self[:] = [None] * length

    def h(self, key, i):
        h1 = key % self.length
        h2 = 1 + (key % (self.length - 1))
        return (h1 + i*h2) % self.length

    def insert(self, key):
        i = 0
        while True:
            h1 = key % self.length
            h2 = 1 + (key % (self.length - 1))
            j = (h1 + i*h2) % self.length
            #j = self.h(key, i)
            if self[j] is None:
                self[j] = key
                return j
            else:
                i += 1
    
    def search(self, key):
        i = 0
        while True:
            h1 = key % self.length
            h2 = 1 + (key % (self.length - 1))
            j = (h1 + i*h2) % self.length
            #j = self.h(key, i)
            if self[j] == key:
                return j
            elif self[j] is None or i >= self.length:
                return None
            else:
                i += 1

def getNum(char):
    char2num = str.maketrans("ACGT", "1234")
    return int(char.translate(char2num), 5)

if __name__ == '__main__':

    n = int(input())
    T = HashTable(1046527)
    C = [input().split(" ") for i in range(n)]
    
    for command, char in C:
        num = getNum(char)
        if command[0] == "i":
            T.insert(num)
        else:
            if T.search(num) is None:
                print("no")
            else:
                print("yes")
### BUGGY CODE ###

class BIT():
    def __init__(self,n):
        self.BIT=[0]*(n+1)
        self.num=n

    def query(self,idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        while idx <= self.num:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

import sys

input=sys.stdin.readline

N,M=map(int,input().split())
q={i:[] for i in range(1,M+1)}
for i in range(N):
    l,r=map(int,input().split())
    q[l].append(r)

query={i:[] for i in range(1,M+1)}
qans={}
for i in range(1,M+1):
    for j in range(1,M//i):
        query[i*j].append(i*j+i)
        qans[(i*j,i*j+i)]=0

bit=BIT(M)
for i in range(1,M+1):
    for r in q[i]:
        bit.update(r,1)
    for r in query[i]:
        qans[(i,r)]=bit.query(r-1)-bit.query(i-1)

imos=[0 for i in range(M+2)]
for i in range(1,M+1):
    for r in q[i]:
        imos[i]+=1
        imos[r+1]-=1

for i in range(1,M+1):
    imos[i]+=imos[i-1]

for i in range(1,M+1):
    res=imos[i*(M//i)]
    for j in range(M//i,1,-1):
        res+=qans[(i*j-i,i*j)]
    print(res)

### FIXED CODE ###

class BIT():
    def __init__(self,n):
        self.BIT=[0]*(n+1)
        self.num=n

    def query(self,idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        while idx <= self.num:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

import sys

input=sys.stdin.readline

N,M=map(int,input().split())
q={i:[] for i in range(1,M+1)}
imos=[0 for i in range(M+2)]
for i in range(N):
    l,r=map(int,input().split())
    q[l].append(r)
    imos[l]+=1
    imos[r+1]-=1
for i in range(1,M+1):
    imos[i]+=imos[i-1]
res={i:imos[i*(M//i)] for i in range(1,M+1)}

query={i:[] for i in range(1,M+1)}
for i in range(1,M+1):
    for j in range(1,M//i):
        query[i*j].append(i*j+i)

bit=BIT(M)
for i in range(1,M+1):
    for r in q[i]:
        bit.update(r,1)
    for r in query[i]:
        res[r-i]+=bit.query(r-1)-bit.query(i-1)

for i in range(1,M+1):
    print(res[i])
### BUGGY CODE ###

import numpy as np
import math


N = int(input())
A = np.array(list(map(int, input().split())))
CumA = np.cumsum(A)

res = 10 ** 16
for i in range(2, N-1):
    idx1 = np.argmin(np.abs(CumA[i-1] - 2 * CumA[:i]))
    P, Q = CumA[idx1], CumA[i-1] - CumA[idx1]
    idx2 = np.argmin(np.abs(CumA[-1] - 2 * CumA[i:] + CumA[i-1]))
    R, S = CumA[i + idx2] - CumA[i-1], CumA[-1] - CumA[i + idx2]
    res = min(res, max([P, Q, R, S]) - min([P, Q, R, S]))
print(res)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np

d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


def left_diff(array):
    """
    array: ordered ndarray, len(array) >= 2
    """
    x = (array[-1] + 1) >> 1
    mid = np.searchsorted(array, x)
    if abs(array[-1] - array[mid] * 2) < abs(array[-1] - array[mid-1] * 2):
        return array[mid], array[-1] - array[mid]
    else:
        return array[mid-1], array[-1] - array[mid-1]


def right_diff(array, offset):
    """
    array: ordered ndarray, len(array) >= 2
        target array or list

    offset: int
        offset value for right array
    """
    x = (array[-1] - offset + 1) >> 1
    mid = np.searchsorted(array, x + offset)
    if abs(array[-1] - array[mid] * 2 + offset)\
            < abs(array[-1] - array[mid-1] * 2 + offset):
        return array[mid] - offset, array[-1] - array[mid]
    else:
        return array[mid-1] - offset, array[-1] - array[mid-1]


def calc_max_diff(p, q, r, s):
    return max(p, q, r, s) - min(p, q, r, s)


if __name__ == '__main__':
    N = d_in()
    a_array = np.array(ds_in())

    cum_a = np.cumsum(a_array)
    left_cut_points = (cum_a[1:-2] + 1) // 2
    left_mid_points = np.searchsorted(cum_a, left_cut_points)
    right_cut_points = (cum_a[-1] + cum_a[1:-2] + 1) // 2
    right_mid_points = np.searchsorted(cum_a, right_cut_points)
    
    ans = float('inf')
    for i in range(2):
        for j in range(2):
            P = cum_a[left_mid_points-i]
            Q = cum_a[1:-2] - P
            R = cum_a[right_mid_points-j] - cum_a[1:-2]
            S = cum_a[-1] - cum_a[right_mid_points-j]
            MAX = np.maximum(np.maximum(P, Q), np.maximum(R, S))
            MIN = np.minimum(np.minimum(P, Q), np.minimum(R, S))
            ans = min(ans, (MAX - MIN).min())

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

N = int(input())
A = [int(input()) for _ in range(N)]
A_max = max(A)
for i in range(N):
    if A[i] != A_max:
        print(A_max)
    else:
        B = A.copy()
        del B[i]
        print(max(B))

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
B = sorted(A,reverse=True)
for i in range(N):
    if A[i] == B[0]:
        print(B[1])
    else:
        print(B[0])
### BUGGY CODE ###

import collections
from collections import Counter
n=int(input())
s=[input() for i in range(n)]
s=Counter(s)
p=[]
p.append(s.most_common()[0][0])
for i in range(len(collections.Counter(s))-1):
    if s.most_common()[i][1]==s.most_common()[i+1][1]:
        p.append(s.most_common(i+2)[i+1][0])
    else:
        break
p=sorted(p)
for i in range(len(p)):
    print(p[i])


### FIXED CODE ###

import collections
from collections import Counter
n=int(input())
s=[input() for i in range(n)]
s=Counter(s)
p=[]
k=s.most_common()
p.append(k[0][0])
for i in range(len(collections.Counter(s))-1):
    if k[i][1]==k[i+1][1]:
        p.append(k[i+1][0])
    else:
        break
p=sorted(p)
for i in range(len(p)):
    print(p[i])
### BUGGY CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

s = input()
k = INT()
a = set()
for i in range(len(s)):
    t = s[i]
    a.add(t)
    if i < len(s) - 1:
        for j in range(i+1, len(s)):
            t += s[j]
            a.add(t)
b = sorted(list(a))
print(b[k-1])

### FIXED CODE ###

from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

s = input()
k = INT()
a = set()
for i in range(len(s)):
    t = s[i]
    a.add(t)
    if i < len(s) - 1:
        for j in range(i+1, min(i+k+1,len(s))):
            t += s[j]
            a.add(t)
b = sorted(list(a))
print(b[k-1])
### BUGGY CODE ###

n = int(input())
num_list = list(map(int, input().split()))
out = "YES"
for j in range(len(num_list)):
    for k in num_list[j + 1:]:
        out = "NO" if num_list[j] == k else out
print(out)


### FIXED CODE ###

n = int(input())
num_list = list(map(int, input().split()))
out = "YES" if len(num_list) == len(set(num_list)) else "NO"
print(out)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n = int(readline())
a = list(map(int, readline().split()))
mod = 10 ** 9 + 7
bit = [0] * 61
ans = 0
for aa in a:
    for j, check in enumerate(bin(aa)[2:][::-1]):
        if check == '1':
            bit[j] += 1
for i, b in enumerate(bit):
    ans += pow(2, i, mod) * ((n - b) * b % mod)
    ans %= mod
print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

n = int(readline())
a = np.array(read().split(), np.int64)
ans = 0
mod = 10 ** 9 + 7
for i in range(63):
    b = (a >> i) & 1
    x = np.count_nonzero(b)
    y = n - x
    x *= y
    for j in range(i):
        x *= 2
        x %= mod
    ans += x
print(ans % mod)
### BUGGY CODE ###

s = input().rstrip()
k = int(input())
slist = []
for i in range(len(s)):
    for j in range(i,len(s)):
        if s[i:j+1] not in slist:
            slist.append(s[i:j+1])
slist.sort()
print(slist[k-1])

### FIXED CODE ###

s = input().rstrip()
k = int(input())
result = []
for i in range(len(s)):
  for j in range(i+1,i+k+1):
    if j <= len(s) and s[i:j] not in result:
      result.append(s[i:j])
result.sort()
print(result[k-1])