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

MOD = 10 ** 9 + 7


def ncr(n, r, mod=MOD):
    return (fct[n] * invf[r] * invf[n - r]) % mod


def make_tables(n, mod=MOD):
    fct = [1 for _ in range(n + 1)]
    invf = [1 for _ in range(n + 1)]

    for i in range(2, n + 1):
        fct[i] = (fct[i - 1] * i) % mod
        invf[i] = divmod(fct[i])
    return fct, invf


def divmod(a, mod=MOD):
    return pow(a, mod - 2, mod)


N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
for i in range(N):
    A[i] %= MOD

fct, invf = make_tables(N, mod=MOD)

ans = 0
test_cnt = 0
for i in range(N - K + 1):
    for j in range(i + K - 1, N):
        if K <= 2:
            ans += (A[j] - A[i]) % MOD
        else:
            test_cnt += ncr(j - i - 1, K - 2)
            ans += ((A[j] - A[i]) % MOD * ncr(j - i - 1, K - 2)) % MOD
print(ans % MOD)



### FIXED CODE ###

MOD = 10 ** 9 + 7

def ncr(n, r, mod=MOD):
    return (fct[n] * invf[r] * invf[n - r]) % mod


def make_tables(n, mod=MOD):
    fct = [1 for _ in range(n + 1)]
    invf = [1 for _ in range(n + 1)]

    for i in range(2, n + 1):
        fct[i] = (fct[i - 1] * i) % mod
        invf[i] = divmod(fct[i])
    return fct, invf


def divmod(a, mod=MOD):
    return pow(a, mod - 2, mod)


N, K = map(int, input().split())
A = sorted(list(map(int, input().split())))
for i in range(N):
    A[i] %= MOD

fct, invf = make_tables(N, mod=MOD)

ans = 0
for i in range(N - K + 1):
    ans += ((A[-1-i] - A[i]) % MOD * ncr(N - i - 1, K - 1)) % MOD
print(ans % MOD)
### BUGGY CODE ###

n, m = map(int, input().split())
mod = 10 ** 9 + 7
a = []
for i in range(m):
    a.append(int(input()))

pat = [1]
zero = False
for i in range(1, n + 1):
    if i - 1 in a and i - 2 in a:
        zero = True
        break
    if i in a:
        pat.append(0)
        continue
    cnt = 0
    if i - 1 not in a:
        cnt += pat[i - 1] % mod
    if i - 2 >= 0 and i - 2 not in a:
        cnt += pat[i - 2] % mod
    pat.append(cnt % mod)

if zero:
    print(0)
else:
    print(pat[n])


### FIXED CODE ###

n, m = map(int, input().split())
mod = 10 ** 9 + 7
pat = [0] * (n + 2)
pat[0] = 1
pat[1] = 1

for i in range(m):
    a = int(input())
    pat[a] = -1

for i in range(2, n + 1):
    if pat[i] < 0:
        continue
    if pat[i - 1] > 0:
        pat[i] = (pat[i] + pat[i - 1]) % mod
    if pat[i - 2] > 0:
        pat[i] = (pat[i] + pat[i - 2]) % mod

print(pat[n])
### BUGGY CODE ###

n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
d = []
b_sum = 0
for _ in range(m):
  b,c = map(int,input().split())
  d.extend([c]*b)
  b_sum += b
d.sort(reverse =True)
d_big = d[:n]


for x in range(min(b_sum,n)):
  if d_big[x] > a[x]:
    a[x] = d_big[x]
  else:
    break

print(sum(a))
  

### FIXED CODE ###

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

bc.sort(key = lambda x: x[1],reverse = True)
i = 0
j = 0
ad = []
while i < n and j < m:
    ad.extend([bc[j][1]]*bc[j][0])
    i += bc[j][0]
    j += 1
    
if len(ad) < n:
    ad.extend([0]*(n-len(ad)))

a.sort(reverse = True)

i = 0
j = 0
k = 0
ans = 0
while k < n :
    if a[i] > ad[j]:
        ans += a[i]
        i += 1
        k += 1
    else:
        ans += ad[j]
        j += 1
        k += 1
  
print(ans)
### BUGGY CODE ###

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

A.sort()
F.sort(reverse = True)
Amax = A[-1]
Fmax = F[0]

x=0
if sum(A) < K:
    x = 0
else:
    xl = 0
    xh = Amax*Fmax
    while xh-xl > 0:
        xm = int((xl+xh)//2)
        if sum(max(A[i]-xm//F[i] ,0) for i in range(0,N)) > K: 
            xl = xm + 1
        else: 
            xh = xm
    else:
        x = xl
print(x)            


### FIXED CODE ###

import numpy as np

N,K = map(int,input().split())
A = np.sort(list(map(int,input().split())))
F = np.sort(list(map(int,input().split())))[::-1]

Amax = A[-1]
Fmax = F[0]

x=0
if sum(A) < K:
    x = 0
else:
    xl = 0
    xh = Amax*Fmax
    while xh-xl > 0:
        xm = int((xl+xh)//2)
        AF = A-xm//F 
        if np.sum(AF[AF>0]) > K: 
            xl = xm + 1
        else: 
            xh = xm
    else:
        x = xl
print(x)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np
from numba import njit


def read():
    N = int(input().strip())
    XYP = np.empty((N, 3), dtype=np.int32)
    for i in range(N):
        XYP[i] = np.fromstring(input().strip(), sep=" ")
    return N, XYP


@njit
def solve(N, XYP, INF=10**18):
    ans = np.full(N+1, INF, dtype=np.int64)
    vcost = np.zeros((N, 2**N), dtype=np.int32)
    hcost = np.zeros((N, 2**N), dtype=np.int32)

    # check 2**N pairs
    for intptn in range(2**N):
        for i in range(N):
            xi, yi, pi = XYP[i]
            v = abs(xi)
            h = abs(yi)
            for j in range(N):
                xj, yj, pj = XYP[j]
                if (intptn >> j) & 1 == 1:
                    v = min(v, abs(xj-xi))
                    h = min(h, abs(yj-yi))
            vcost[i, intptn] += v
            hcost[i, intptn] += h

    # check 3**N pairs
    for intptn in range(3**N):
        # split into two 2**N pairs
        p, intvptn, inthptn = intptn, 0, 0
        u = 0
        for i in range(N):
            if p % 3 == 1:
                intvptn += 1 << (N-i-1)
                u += 1
            elif p % 3 == 2:
                inthptn += 1 << (N-i-1)
                u += 1
            p //= 3
        s = 0
        for i in range(N):
            s += min(vcost[i, intvptn], hcost[i, inthptn]) * XYP[i, 2]
        ans[u] = min(ans[u], s)
    
    return ans


if __name__ == '__main__':
    inputs = read()
    ans = solve(*inputs)
    for a in ans:
        print(a)


### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
from numba import njit


def read():
    N = int(input().strip())
    XYP = np.empty((N, 3), dtype=np.int32)
    for i in range(N):
        XYP[i] = np.fromstring(input().strip(), sep=" ")
    return N, XYP


@njit
def solve(N, XYP, INF=10**18):
    ans = np.full(N+1, INF, dtype=np.int64)
    vcost = np.zeros((2**N, N), dtype=np.int32)
    hcost = np.zeros((2**N, N), dtype=np.int32)

    # check 2**N pairs
    for intptn in range(2**N):
        for i in range(N):
            xi, yi, pi = XYP[i]
            v = abs(xi)
            h = abs(yi)
            for j in range(N):
                xj, yj, pj = XYP[j]
                if (intptn >> j) & 1 == 1:
                    v = min(v, abs(xj-xi))
                    h = min(h, abs(yj-yi))
            vcost[intptn, i] += v
            hcost[intptn, i] += h

    # check 3**N pairs
    for intptn in range(3**N):
        # split into two 2**N pairs
        p, intvptn, inthptn = intptn, 0, 0
        u = 0
        for i in range(N):
            if p % 3 == 1:
                intvptn += 1 << (N-i-1)
                u += 1
            elif p % 3 == 2:
                inthptn += 1 << (N-i-1)
                u += 1
            p //= 3
        s = 0
        for i in range(N):
            s += min(vcost[intvptn, i], hcost[inthptn, i]) * XYP[i, 2]
        ans[u] = min(ans[u], s)
    
    return ans


if __name__ == '__main__':
    inputs = read()
    ans = solve(*inputs)
    for a in ans:
        print(a)
### BUGGY CODE ###

n = int(input())
num = n

while num % 2 != 0 or num % n != 0:
    num += 1

print(num)


### FIXED CODE ###

a = int(input())
b = 2
x = a * b

if a < b:
    tmp = a
    a = b
    b = tmp

r = a % b
while r != 0:
    a = b
    b = r
    r = a % b

print(int(x/b))
### BUGGY CODE ###

import heapq
import math
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
F = list(map(int, sys.stdin.readline().split()))

if N == 1:
    a = A[0]
    f = F[0]
    ans = max(a - K, 0) * f
    print(ans)
    exit()

A.sort()
F.sort(reverse=True)

heap = []
for a, f in zip(A, F):
    heap.append((-a * f, a, f))
heapq.heapify(heap)

while K > 0:
    _, a, f = heapq.heappop(heap)
    if a == 0:
        break
    af2 = -heap[0][0]
    next_a = max(0, math.ceil(af2 / f) - 1)
    k = min(K, a - next_a)
    K -= k
    a -= k
    heapq.heappush(heap, (-a * f, a, f))

ans = 0
for af, _, _ in heap:
    ans = max(ans, -af)
print(ans)


### FIXED CODE ###

import heapq
import math
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
F = list(map(int, sys.stdin.readline().split()))

if N == 1:
    a = A[0]
    f = F[0]
    ans = max(a - K, 0) * f
    print(ans)
    exit()

A = np.array(A, dtype=int)
F = np.array(F, dtype=int)
A.sort()
F.sort()
F = F[::-1]


def required_k(score):
    # score を出すために必要な K
    return np.ceil(np.maximum(A - score / F, 0)).sum()


ok = (A * F).max()
ng = -1
while abs(ok - ng) > 1:
    score = (ok + ng) // 2
    if required_k(score) <= K:
        ok = score
    else:
        ng = score
print(ok)
### BUGGY CODE ###

import math
n,d = map(int,input().split())

y = list()
x = list()
xy = list()

for i in range(n):
    xy += map(int,input().split())

#xy_2 = int(len(xy) / 2)
#for i in range(xy_2):
#    x.append(xy.pop(0))
#    y.append(xy.pop(0))

ans = 0
for i in range(n):
    if d >= math.sqrt(xy.pop(0)**2 + xy.pop(0)**2):
        ans += 1

print(ans)

### FIXED CODE ###

n,d = map(int,input().split())
d2 = d ** 2

xy2 = list()
for i in range(n):
    x,y = map(int,input().split())
    xy2.append(x**2+y**2)

    ans = 0
for i in xy2:
    if d2 >= i:
        ans += 1
print(ans)
### BUGGY CODE ###

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

for k in range(n):
  for i in range(n):
    for j in range(n):
      if a[i][j]>a[i][k]+a[k][j]:
        print(-1)
        exit(0)

ans=0
for i in range(n):
  for j in range(i+1,n):
    ok=True
    for k in range(n):
      if i==k or j==k:
        continue
      if a[i][j]==a[i][k]+a[k][j]:
        ok=False
        break
    if ok:
        ans+=a[i][j]
print(ans)


### FIXED CODE ###

# ABC074 D - Restoring Road Network
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]

for k in range(n):
    for i in range(n):
        for j in range(n):
            if a[i][j]>a[i][k]+a[k][j]:
                print(-1)
                exit()
"""
a[i][j]が、i,kを除く全てのkについて
a[i][j]<a[i][k]+a[k][j]なら
a[i][j]は最短経路となる。
"""
ans=0
for i in range(n):
    for j in range(i+1,n):
        # iとjの間に辺が存在する場合True
        flg=True
        for k in range(n):
            if i==k or j==k:
                continue
            if a[i][j]==a[i][k]+a[k][j]:
                flg=False
                break
        if flg:
            ans+=a[i][j]
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
H_list = list(map(int, input().split()))
N_list = [[0] * N for _ in range(N)]
for _ in range(M):
  A, B = map(int, input().split())
  N_list[A-1][B-1] = 1
  N_list[B-1][A-1] = 1

def search(N_list, H_list, n, ans):
  w_flag = True
  for i in range(len(N_list[n])):
    if N_list[n][i] == 1:
      if H_list[n] <= H_list[i]:
        w_flag = False
        N_list[n][n] = 1
        if N_list[i][i] != 1:
          ans = search(N_list, H_list, i, ans)
      else:
        N_list[i][i] = 1
  if w_flag:
    ans += 1
    N_list[n][n] = 1
  return ans

ans = 0    
for n in range(N):
  if N_list[n][n] == 0:
    ans = search(N_list, H_list, n, ans)
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
H_list = list(map(int, input().split()))
N_list = [0] * N
for _ in range(M):
  A, B = map(int, input().split())
  if H_list[A-1] >= H_list[B-1]:
    N_list[B-1] = 1
  if H_list[A-1] <= H_list[B-1]:
    N_list[A-1] = 1
print(N_list.count(0))
### BUGGY CODE ###

x, y, z, k = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list((map(int,input().split())))
D = []
E = []
for i in range(x):
  for j in range(y):
    D.append(A[i]+B[j])
D.sort()
for i in range(z):
  for j in range(min(len(D),k)):
    E.append(C[i]+D[::-1][j])
print("\n".join(map(str,sorted(E)[::-1][:k])))


### FIXED CODE ###

x, y, z, k = [int(n) for n in input().split()]
va = sorted([int(n) for n in input().split()], reverse=True)
vb = sorted([int(n) for n in input().split()], reverse=True)
xy = min(x*y, k)
vab = (sorted([a + b for a in va for b in vb], reverse=True))[:xy]
vc = sorted([int(n) for n in input().split()], reverse=True)
xyz = min(x*y*z, k)
print(*((sorted([ab + c for ab in vab for c in vc], reverse=True))[:xyz]), sep="\n")
### BUGGY CODE ###

n = int(input())
x = int(input(), 2)

def solve(a):
    pc = bin(a).count('1')
    if pc == 0:
        return 0
    elif pc == 1:
        return 1
    return solve(a % pc) + 1
        
for i in reversed(range(n)):
    a = 1 << i ^ x
    print(solve(a))


### FIXED CODE ###

n = int(input())
x_bin = input()
x = int(x_bin, 2)

pc = x_bin.count('1')
pc_p = pc + 1
pc_m = pc - 1

if pc == 1:
    for i, v in enumerate(x_bin):
        if v == '1':
            print(0)
        else:
            if i != n-1:
                if x_bin[-1] == '0':
                    print(1)
                else:
                    print(2)
            else:
                print(2)
    exit()

p = {0: 1}
m = {0: 1}
for i in range(1, n):
    p[i] = p[i-1]*2 % pc_p
    m[i] = m[i-1]*2 % pc_m

rest = {0: 0}
for i in range(1, pc + 1):
    rest[i] = rest[i % bin(i).count('1')] + 1

x_p = x % pc_p
x_m = x % pc_m

for i in range(n, 0, -1):
    if x_bin[n-i] == '1':
        a = (x_m - m[i-1]) % pc_m
        print(rest[a] + 1)
    else:
        a = (x_p + p[i-1]) % pc_p
        print(rest[a] + 1)
### BUGGY CODE ###

s = list(input())

cached = []
candidate = ''
prev = ''
while len(s) > 0:
  candidate += s.pop(0)
  if candidate != prev:
    cached.append(candidate)
    prev = candidate
    candidate = ''

print(len(cached))


### FIXED CODE ###

from collections import deque
s = deque(list(input()))

cached = []
candidate = ''
prev = ''
cnt = 0
while len(s) > 0:
  candidate += s.popleft()
  if candidate != prev:
    prev = candidate
    candidate = ''
    cnt += 1

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

import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
import math
from functools import reduce

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]

k = int(input())
def gcd(*numbers):
    return reduce(math.gcd, numbers)

count = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            count += gcd(i,j,l)
print(count)

### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
import math
from functools import reduce
import numpy as np

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]

k = int(input())
def gcd(*numbers):
    return reduce(math.gcd, numbers)

count = 0
a = []
for i in range(1,k+1):
    for j in range(1,k+1):
        a = math.gcd(i,j)
        for l in range(1,k+1):
            count += math.gcd(a,l)
print(count)
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
# dp[i] 足場iに辿り着くまでに支払うコストの総和の最小値
# dp[0] = 0, dp[1] = 0, dp[2] = abs(h[1] - h[0])
dp = [float("inf") for i in range(N+1)]
dp[0] = 0; dp[1] = 0
dp[2] = abs(h[1] - h[0])
for i in range(3,N+1):
    for j in range(1,min(i,K+1)):
        if dp[i-j] + abs(h[i-1] - h[i-j-1]) < dp[i]:
            dp[i] = dp[i-j] + abs(h[i-1] - h[i-j-1])
print(dp[N])

### FIXED CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
# dp[i] 足場iに辿り着くまでに支払うコストの総和の最小値
# dp[0] = 0, dp[1] = 0, dp[2] = abs(h[1] - h[0])
dp = [float("inf") for i in range(N+1)]
dp[0] = 0; dp[1] = 0
dp[2] = abs(h[1] - h[0])
for i in range(3,N+1):
    for j in range(1,min(i,K+1)):
        if dp[i-j] + abs(h[i-1] - h[i-j-1]) < dp[i]:
            dp[i] = dp[i-j] + abs(h[i-1] - h[i-j-1])
print(dp[N])
### BUGGY CODE ###

#!/usr/bin/python3
# abc121_c

"""
Energy Drink Collector
"""
test = False


def main():
    """
    とにかく安い方からM本になるまで買い続ける。
    """
    N, M = map(int, input().split())
    l = []

    for _ in range(N):
        # 安い順に、値段だけのリストをつくる。[100, 100, 100, 110, 120, 120, ...]
        tempA, tempB = map(int, input().split())
        l.extend([tempA] * tempB)

    # 安い順に並べる
    l.sort()
    if test:
        print(l)

    # 買う。
    cost = sum(l[0:M])

    # 合計金額を出力
    print(cost)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/python3
# abc121_c

"""
Energy Drink Collector
"""
test = False


def main():
    """
    とにかく安い方からM本になるまで買い続ける。
    """
    N, M = map(int, input().split())
    l = []
    bottle = 0
    cost = 0

    for _ in range(N):
        # [値段, 在庫本数] の2xNリストをつくる。
        l.append(list(map(int, input().split())))

    # 安い順に並べる
    l.sort()
    # 安い店の在庫を全部買って、M本を超えたら中断

    for i in range(N):
        bottle += l[i][1]
        cost += l[i][0] * l[i][1]
        # 買いすぎた分を返品
        if bottle >= M:
            cost -= (bottle - M) * l[i][0]
            break

    # 合計金額を出力
    print(cost)


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

N, A = map(int, input().split())  # N枚数のカード, 平均をAにしたい
X = tuple(map(int, input().split()))  # N枚のカードの中身

dp = [[[0]*(50*N+2) for _ in range(N+2)] for _ in range(N+2)]

dp[0][0][0] = 1  # 0枚の中から0枚選んで合計が0になる選び方が1通りある

for i in range(N):
    for j in range(N+1):
        for k in range(50*N+1):
            # if dp[i][j][k]:  # ここの分岐が分からん
            if k+X[i] < 50*N+2:
                dp[i+1][j][k] += dp[i][j][k]
                dp[i+1][j+1][k+X[i]] += dp[i][j][k]
ans = 0
for i in range(1, N+1):
    ans += dp[N][i][i*A]
print(ans)


### FIXED CODE ###

N, A = map(int, input().split())  # N枚数のカード, 平均をAにしたい
X = tuple(map(int, input().split()))  # N枚のカードの中身

dp = [[[0]*(50*N+1) for _ in range(N+1)] for _ in range(N+1)]

dp[0][0][0] = 1  # 0枚の中から0枚選んで合計が0になる選び方が1通りある

for i in range(N):
    for j in range(N+1):
        for k in range(50*N+1):
            if dp[i][j][k]:  # そのパターン数が0になっている場所からの遷移はありえない！！！
                dp[i+1][j][k] += dp[i][j][k]
                dp[i+1][j+1][k+X[i]] += dp[i][j][k]
ans = 0
for i in range(1, N+1):
    ans += dp[N][i][i*A]
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = sorted(a)
maxcomb = 0
x=0
def comb(n,r):
    npr = 1
    rp1 = 1
    for i in range(n-r+1,n+1):
        npr *= i
    for j in range(1,r+1):
        rp1 *= j
    return npr // rp1

comb(10,2)

for i in range(0,n):
    if maxcomb < comb(max(b),b[i]):
        maxcomb = comb(max(b),b[i])            
        x=b[i]
print(max(b),x)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = sorted(a)
maxb = max(b)
mini = b[0]
for i in b:
    if abs(maxb/2 - i) < abs(maxb/2 - mini):
        mini = i
print(maxb,mini)
### BUGGY CODE ###

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

class Node():
    def __init__(self, key, prev=None, nex=None):
        self.key = key
        self.prev = prev
        self.next = nex
    
class DoublyLinkedLiset():
    def __init__(self):
        self.nil = Node(None)
        self.nil.next = self.nil
        self.nil.prev = self.nil
    
    def insert(self, x):
        X = Node(x)
        X.next = self.nil.next
        self.nil.next.prev = X
        self.nil.next = X
        X.prev = self.nil

    def listSearch(self, x):
        cur = self.nil.next
        while (cur != self.nil and cur.key != key):
            cur = cur.next
        
        return cur

    def deleteNode(self, X):
        if X == self.nil:
            return
        X.prev.next = X.next
        X.next.prev = X.prev
        del X

    def deleteFirst(self):
        self.deleteNode(self.nil.next)

    def deleteLast(self):
        self.deleteNode(self.nil.prev)

    def deleteKey(self, x):
        self.deleteNode(self.listSearch(x))

    def printList(self):
        cur = self.nil.next
        ret = []
        
        while cur.key is not None:
            ret.append(cur.key)
            cur = cur.next
  
        return ' '.join(ret)

if __name__ == '__main__':

    n = int(input())
    dll = DoublyLinkedLiset()

    for i in range(n):
        line = input().split(" ")
        if len(line) == 2:
            command, key = line
            if command == "insert":
                dll.insert(key)
            elif command == "delete":
                dll.deleteKey(key)

        else:
            command = line[0]
            if command == "deleteFirst":
                dll.deleteFirst()
            elif command == "deleteLast":
                dll.deleteLast()

    print(dll.printList())
    



### FIXED CODE ###

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

from collections import deque

if __name__ == '__main__':
    n = int(input())
    L = deque()

    for _ in range(n):
        command = input().split(" ")
        if command[0] == "insert":
            L.appendleft(command[1])
        elif command[0] == "delete":
            try:
                L.remove(command[1])
            except:
                pass
        elif command[0] == "deleteFirst":
            L.popleft()
        elif command[0] == "deleteLast":
            L.pop()

    print(" ".join(L))
### BUGGY CODE ###

def all_index(s, c):
    ins = []
    for i in range(len(s)):
        if s[i] == c:
            ins.append(i)

    return ins


s = input().strip()
k = int(input())

ss = set()
alphabets = sorted(list(set(s)))
for c in alphabets:
    ins = all_index(s, c)
    for i in ins:
        for j in range(i, len(s)):
            ss.add(s[i:j+1])

    if len(ss) >= k:
        break

print(sorted(list(ss))[k-1])

### FIXED CODE ###

def all_index(s, c):
    ins = []
    for i in range(len(s)):
        if s[i] == c:
            ins.append(i)

    return ins


s = input().strip()
k = int(input())

ss = set()
alphabets = sorted(list(set(s)))
for c in alphabets:
    ins = all_index(s, c)
    for i in ins:
        for j in range(i, len(s)):
            if (j+1 - i) > k:
                break

            ss.add(s[i:j+1])

    if len(ss) >= k:
        break

print(sorted(list(ss))[k-1])