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

import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 = list(map(int,sys.stdin.readlines())) #縦入力
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""
n,m =  map(int, sys.stdin.readline().split())

dp=[0]*(n+1)
list_a = list(map(int,sys.stdin.readlines()))

dp[0]=1

for i in range(1,n+1):
    dp[i] = (dp[i-1] + dp[i-2]) % big_prime #dp[-1]=0
    if i in list_a:
        dp[i]=0
ans = dp[n]
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

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

n = int(input())

a = list(map(lambda x:int(x), input().split()))

#junban = []

for i in range(n):
    jun = a.index(i+1)
    #junban.append(jun+1)
    if i != n:
        print(jun+1," ",end="")
    else:
        print(jun+1)


### FIXED CODE ###

n = int(input())

a = list(map(lambda x:int(x), input().split()))

junban = []
for i in range(n):
    junban.append(0)

for i in range(n):
    junban[a[i]-1] = str(i+1)



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

n =int(input())
a=list(map(int, input().split()))
m=0
s=[]
for i in range(len(a)):
    m+=a[i]
    if len(s)!=0:
        mins=min(s)
    s.append(abs(sum(a)-m*2))
    if len(s)!=1 and mins<s[i]:
        break
print(mins)

### FIXED CODE ###

n =int(input())
a=list(map(int, input().split()))
m=0
s=[]
suma=sum(a)
for i in range(len(a)):
    m+=a[i]
    s.append(abs(suma-m*2))
print(min(s))
### BUGGY CODE ###

S = input()
Scount = 0
Slen = len(S)
for i in range(Slen-1):
    for j in range(1,Slen):
        if (i+j)<=Slen:
            part_S = S[i:i+j]
            num = int(part_S)
            if num % 673 == 0:
                num = num//673
                if num % 3 ==0:
                    Scount += 1
print(Scount)

### FIXED CODE ###

S = input()
from collections import defaultdict
d = defaultdict(int)
before = 0
for i in range(1,len(S)+1):
    now = (int(S[-i])*pow(10,i,2019)+before) % 2019
    d[now] += 1
    before = now
d[0] += 1
ans = 0
for i in d.values():
    ans += i*(i-1)//2
print(ans)
### BUGGY CODE ###

N = int(input())
L = [int(x) for x in input().split()]
L = sorted(L)
ans = 0
for one in range(N - 2):
    for two in range(one+1, N - 1):
        for three in range(two + 1, N):
            if L[one] + L[two] > L[three]:
                ans += 1
print(ans)


### FIXED CODE ###

import bisect
N = int(input())
L = [int(x) for x in input().split()]
L = sorted(L)
ans = 0
for one in range(N - 2):
    for two in range(one+1, N-1):
        ans += bisect.bisect_left(L, (L[one] + L[two]))-two-1
        #print(bisect.bisect_left(L, (L[one] + L[two]))-two-1)
print(ans)
### BUGGY CODE ###

k,s = map(int,input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z == s:
                ans += 1
print(ans)

### FIXED CODE ###

k,s = map(int,input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if 0 <= z and z <= k:
            ans += 1
print(ans)
### BUGGY CODE ###

from heapq import heappop, heappush


class median_o1:
    def __init__(self):
        self.count = 0
        self.al = []
        self.ar = []
        self.sl = 0
        self.sr = 0
        self.b = 0

    def update_b(self, b):
        self.b += b

    def insert(self, x):
        if self.count % 2 == 0:
            if self.count == 0:
                heappush(self.al, -x)
                self.sl += x
            else:
                t = heappop(self.ar)
                self.sr -= t
                tl, tr = min(x, t), max(x, t)
                heappush(self.al, -tl)
                self.sl += tl
                heappush(self.ar, tr)
                self.sr += tr
        else:
            t = heappop(self.al)
            t *= (-1)
            self.sl -= t
            tl, tr = min(x, t), max(x, t)
            heappush(self.ar, tr)
            self.sr += tr
            heappush(self.al, -tl)
            self.sl += tl
        self.count += 1

    def get_median(self):
        return -self.al[0]

    def calc_min_value(self):
        # print(self.al, self.ar, self.b, self.sl, self.sr)
        m = self.get_median()
        return (m * ((self.count + 1) // 2) - self.sl) + (self.sr - m * (self.count // 2)) + self.b


q = int(input())

m = median_o1()

for _ in range(q):
    q_typ, *x = tuple(map(int, input().split()))
    # 1, [a, b]
    # 2, []
    if q_typ == 1:
        m.update_b(x[1])
        m.insert(x[0])
    else:
        print(m.get_median(), m.calc_min_value())


### FIXED CODE ###

from heapq import heappush, heappop

Q = int(input())

update_count = 0
al = []
sl = 0
ar = []
sr = 0
b = 0
for _ in range(Q):
    # print(f'al:{al}, sl:{sl}')
    # print(f'ar:{ar},sr:{sr}')
    # print(f'b:{b}')
    # print()
    s = tuple(map(int, input().split()))
    if s[0] == 1:
        # 更新クエリ
        b += s[2]
        if update_count % 2 == 0:
            # 左に追加
            heappush(ar, s[1])  # 右に追加
            sr += s[1]
            x = heappop(ar)  # 右の最小値
            sr -= x
            heappush(al, -x)  # 左に追加
            sl += x
        else:
            # 右に追加
            heappush(al, -s[1])  # 左に追加
            sl += s[1]
            x = heappop(al)  # 左の最小値
            sl -= (-x)
            heappush(ar, -x)  # 右に追加
            sr += (-x)
        update_count += 1
        # 左キューalの最大値が中央値になっている
        # 左キューにheappushする際,負値に変換したので,heappopで最大値*(-1)が求まる
    else:
        # 求値クエリ
        x = heappop(al)  # 中央値
        heappush(al, x)
        x *= (-1)
        cnt_l = (update_count + 1) // 2
        cnt_r = update_count - cnt_l
        print(x, (cnt_l * x - sl) + (sr - cnt_r * x) + b)
### BUGGY CODE ###

import itertools

N = input()

xlist = input().split(" ")
ylist = []
for num in xlist:
    ylist.append(int(num))
pairs = itertools.combinations(ylist, 2)
answer = 0
for pair in pairs:
    answer += pair[0] * pair[1]

print(answer % (10**9 +7 ))

### FIXED CODE ###



N = int(input())
A = list((input().split(" ")))

values = []
for i in range(N):
    values.append(int(A[i]))


suffixSumArray = values.copy()



for i in range(N-2,-1,-1):
    suffixSumArray[i] = suffixSumArray[i+1] + suffixSumArray[i]



sum = 0
for i in range(N-1):
    sum += (values[i] * suffixSumArray[i+1])

print(sum % (10 ** 9 + 7))
### BUGGY CODE ###

from itertools import product
N,M=map(int,input().split())
l=list(product((0,1),repeat=N))
L=len(l)
for i in range(2**N):
    l[i]=[l[i],1300000]
r=(2048,1024,512,256,128,64,32,16,8,4,2,1)
l[0][1]=0
for i in range(M):
    a,b=map(int,input().split())
    c=tuple(map(int,input().split()))
    t=[0]*N
    for j in c:
        t[-j]=1
    for j in range(L):
        s=0
        for k in range(N):
            if l[j][0][-k-1] or t[-k-1]:
                s+=r[-k-1]
        l[s][1]=min(l[j][1]+a,l[s][1])
if l[-1][1]==1300000:
    print(-1)
else:
    print(l[-1][1])

### FIXED CODE ###

from itertools import product
N,M=map(int,input().split())
l=list(product((0,1),repeat=N))
L=len(l)
for i in range(2**N):
    l[i]=[l[i],1300000]
r=(2048,1024,512,256,128,64,32,16,8,4,2,1)
l[0][1]=0
for i in range(M):
    a,b=map(int,input().split())
    c=tuple(map(int,input().split()))
    t=[0]*N
    for j in c:
        t[-j]=1
    for j in range(L):
        s=0
        for k in range(N):
            if l[j][0][-k-1] or t[-k-1]:
                s+=r[-k-1]
        l[s][1]=min(l[j][1]+a,l[s][1])
if l[-1][1]==1300000:
    print(-1)
else:
    print(l[-1][1])
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
import sys
input=sys.stdin.readline
n,k,l = map(int, input().split())
uf_road = UnionFind(n)
uf_train = UnionFind(n)
for i in range(k):
    p,q=list(map(int, input().split()))
    uf_road.union(p-1, q-1)
for i in range(l):
    p,q=list(map(int, input().split()))
    uf_train.union(p-1, q-1)

ans=[0]*n
for i in range(n):
    if ans[i]!=0:
        continue
    mem1=set(uf_road.members(i))
    mem2=set(uf_train.members(i))
    inter=mem1 & mem2
    int_num=len(inter)
    for tmp in inter:
        ans[tmp]=int_num
print(*ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
import sys
input=sys.stdin.readline
n,k,l = map(int, input().split())
uf_road = UnionFind(n)
uf_train = UnionFind(n)
for i in range(k):
    p,q=list(map(int, input().split()))
    uf_road.union(p-1, q-1)
for i in range(l):
    p,q=list(map(int, input().split()))
    uf_train.union(p-1, q-1)

from collections import defaultdict
d = defaultdict(int)
for i in range(n):
    d[uf_road.find(i), uf_train.find(i)] += 1
print(*(d[uf_road.find(i), uf_train.find(i)] for i in range(n)))
### BUGGY CODE ###

from itertools import combinations as f
l,r=map(int,input().split())
s=set(map(lambda x:x%2019,range(l,r+1)))
print(min([i*j%2019 for i,j in f(s,2)]))

### FIXED CODE ###

from itertools import combinations as f
l,r=map(int,input().split())
s=set(map(lambda x:x%2019,range(l,r+1)[:2019]))
print(min([i*j%2019 for i,j in f(s,2)]))
### BUGGY CODE ###

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

ans = sum([sum(line) for line in graph])
for a in range(n):
    for b in range(n):
        if a == b:
            continue
        for c in range(n):
            if a == c or b == c:
                continue
            if graph[a][b] > graph[a][c] + graph[c][b]:
                print(-1)
                exit()
            elif graph[a][b] == graph[a][c] + graph[c][b]:
                ans -= graph[a][b]

print(ans // 2)

### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline
n = int(input())
G = np.array([list(map(int, input().split())) for _ in range(n)], dtype=float)
use = np.ones((n,n),dtype=bool)
impossible = np.zeros((n,n),dtype=bool)
for w in range(n):
    D = sum(np.meshgrid(G[w], G[w]))
    D[w] = np.inf
    D[:,w] = np.inf
    use &= ~(G == D)
    impossible |= G > D
if impossible.any():
    print(-1)
else:
    print(int(np.sum(G[use]) / 2))
### BUGGY CODE ###

from itertools import permutations
n=int(input())
N=list(map(int,input().split()))
flag=1
ans=[]
for i in list(permutations(N)):
    i=list(i)
    i.insert(0,i[-1])
    i.append(i[1])
    for j in range(1,n):
        if i[j]==i[j-1]^i[j+1]:
            continue
        else:flag=0
    ans.append(flag)

if 1 in ans:print("Yes")
else:print("No")

### FIXED CODE ###

N=int(input())
A = list(map(int,input().split()))
temp = 0
for i in A:
    temp = temp ^ i
if(temp == 0):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

#!/usr/bin/env python3

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

tele = [1,A[0]]
B = [0]
z = 0
s = 0
for i in range(N):
    if z in B and len(B) != 1:
        s = B.index(z)
        break
    tele.append(A[tele[-1]-1])
    B.append(tele[-2]-1)
    z = tele[-1]-1

if K <= s:
    print(tele[K])
else:
    K -= s
    amari = K%(len(tele[s:len(tele)-1]))
    tele = tele[s:len(tele)-1]*2
    print(tele[amari])


### FIXED CODE ###

#!/usr/bin/env python3

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

for i in range(N):
    A[i] -= 1

tele = [0]
#tele = [0,A[0]-1]
z = 0
s = 0
#B = {0:0,A[0]-1:1}
B = {0:0}
for i in range(N):
    if A[tele[-1]] in B and len(B) != 1:
        s = B[A[tele[-1]]]
        break
    B[A[tele[-1]]] = i+1
    tele.append(A[tele[-1]])
    z = tele[-1]

if K <= s:
    print(tele[K]+1)
else:
    K -= s
    amari = K%(len(tele[s:len(tele)]))
    tele = tele[s:len(tele)]*2
    print(tele[amari]+1)
### BUGGY CODE ###

# input
N, K, Q = map(int, input().split())
points = [K] * N
for q in range(Q):
    A = int(input())
    
    # check
    for i, p in enumerate(points):
        if i + 1 == A:
            continue
        points[i] -= 1

for p in points:
    if p > 0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

# input
N, K, Q = map(int, input().split())
points = {}
for i in range(1, N + 1):
    points[i] = 0

for q in range(Q):
    A = int(input())

    # check
    points[A] += 1

# output
for k in points.keys():
    if K - Q + points[k] > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

#!/usr/bin/env python3
s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0 for _ in range(ls+1)] for _ in range(lt+1)]

for i in range(lt):
    for j in range(ls):
        if t[i] == s[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])

ans = ""
ti = lt
sj = ls
while ti > 0 and sj > 0:
    if dp[ti][sj] == dp[ti-1][sj]:
        ti -= 1
    elif dp[ti][sj] == dp[ti][sj-1]:
        sj -= 1
    elif dp[ti][sj] == dp[ti-1][sj-1] + 1:
        ans += t[ti-1]
        ti -= 1
        sj -= 1
print(ans[::-1])


### FIXED CODE ###

#!/usr/bin/env python3
s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0 for _ in range(ls+1)] for _ in range(lt+1)]

for i in range(lt):
    for j in range(ls):
        if t[i] == s[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j])

ans = ""
ti = lt
sj = ls
while ti > 0 and sj > 0:
    if dp[ti][sj] == dp[ti-1][sj]:
        ti -= 1
    elif dp[ti][sj] == dp[ti][sj-1]:
        sj -= 1
    elif dp[ti][sj] == dp[ti-1][sj-1] + 1:
        ans += t[ti-1]
        ti -= 1
        sj -= 1
print(ans[::-1])
### BUGGY CODE ###

N=int(input())
power=1
for i in range(1,N+1):
    power*=i
print(power%(10**9+7))

### FIXED CODE ###

import math
print(math.factorial(int(input()))%(10**9+7))
### BUGGY CODE ###

s = list(input())
q = int(input())
c = 0
for i in range(q):
    qy = list(input().split())
    if qy[0] == "1":
        c += 1
    else:
        if (qy[1] == "1" and c % 2 == 0) or (qy[1] == "2" and c % 2 == 1):
            s = [qy[2]] + s
        else:
            s = s + [qy[2]]
if c % 2 == 0:
    print("".join(s))
else:
    print("".join(reversed(s)))

### FIXED CODE ###

s = input()
q = int(input())
c = 0
t = ""
u = ""
for i in range(q):
    qy = list(input().split())
    if qy[0] == "1":
        c += 1
    else:
        if (qy[1] == "1" and c % 2 == 0) or (qy[1] == "2" and c % 2 == 1):
            t = qy[2] + t
        else:
            u = u + qy[2]
ans = t + s + u
if c % 2 == 0:
    print(t + s + u)
else:
    print(ans[::-1])
### BUGGY CODE ###

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

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

nums.sort(reverse=True)
for i in range(m):
    b, c = map(int, input().split())
    for j in range(b):
        nums.append(c)
        
    nums.sort(reverse=True)
    nums = nums[0:n]

result = 0
for i in nums:
    result = result + i

print(result)

### FIXED CODE ###

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

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

ops = []
for i in nums:
    ops.append([1, i])
    
for i in range(m):
    b, c = map(int, input().split())
    ops.append([b, c])

total = 0
sums = []
for b, c in sorted(ops, key=lambda x:x[1], reverse=True):
    if total > n:
        break
    sums.extend([c]*b)
    total = total + b
print(sum(sums[:n]))
### BUGGY CODE ###

from collections import deque
N, Q = map(int, input().split())
S = input()
l = [0 for i in range(Q)]
r = [0 for i in range(Q)]

for i in range(Q):
    l[i], r[i] = map(int, input().split())

for i in range(Q):
    s = S[l[i]-1:r[i]]
    print(s.count('AC'))

### FIXED CODE ###

n,q = map(int,input().split())
s = list(input())

#a[i]:s[0]~s[i]までに何個ACがあったか
a = [0]*n
#end[i]:s[i]がACの'C'か
end = [False]*n
for i in range(1,n):
    if s[i] == 'C' and s[i-1] == 'A':
        a[i] = a[i-1]+1
        end[i] = True
    else:
        a[i] = a[i-1]

for i in range(q):
    L,R = map(int,input().split())
    L,R = L-1,R-1
    if L == 0:
        print(a[R])
    else:
        if end[L]:
            print(a[R]-a[L-1]-1)
        else:
            print(a[R]-a[L-1])
### BUGGY CODE ###

n = int(input())
slist = [""]*n
for i in range(n):
	slist[i] =sorted(input())
sslist=sorted(slist)
count=0
for i in range(n-1):
	for j in range(i+1,n):
		if sslist[i]==sslist[j]:
			count = count +1
#	print(sslist[i])
print(count)

### FIXED CODE ###

n = int(input())
slist = [""]*n
for i in range(n):
	slist[i] =sorted(input())
sslist=sorted(slist)
count=0
i = 0
while i < n-1:
	j=1
	if sslist[i]==sslist[i+1]:
		j=2
		while i+j<=n-1 and sslist[i]==sslist[i+j]:
			j=j+1
		count=count + j*(j-1)//2
#		print(j)
	i=i+j
#	print(sslist[i])
print(count)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, K = map(int, input().split())
    h = [0] + list(map(int, input().split())) # 便宜上、先頭に[0]

    dp = [1000000007 for _ in range(N+1)] # dp[i]：足場iに移動する最小コスト
    dp[1] = 0 # 初期位置のため、0
    dp[2] = abs(h[2]-h[1]) # 足場2への移動は1パターンのみのため

    for dst in range(3, N+1):
        for k in range(1,K+1):
            src = dst-k
            if src < 1:
                break
            dp[dst] = min(dp[dst], dp[src] + abs(h[dst]-h[src]))
    print(dp[N])

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, K = map(int, input().split())
    h = [0] + list(map(int, input().split())) # 便宜上、先頭に[0]

    dp = [1000000007 for _ in range(N+1)] # dp[i]：足場iに移動する最小コスト
    dp[1] = 0 # 初期位置のため、0
    dp[2] = abs(h[2]-h[1]) # 足場2への移動は1パターンのみのため

    for dst in range(3, N+1):
        for k in range(1,K+1):
            src = dst-k
            if src < 1:
                break
            dp[dst] = min(dp[dst], dp[src] + abs(h[dst]-h[src]))
    print(dp[N])

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

# from collections import deque
import numpy as np
def main():
    n, m, k = map(int, input().split())
    A = np.array([0] + list(map(int, input().split())))
    B = np.array([0] + list(map(int, input().split())))
    X = np.cumsum(A)
    Y = np.cumsum(B)
    P = X[X <= k]
    Q = Y[Y <= k]
    n = len(P)
    m = len(Q)
    # print(P,Q)

    cnt = 0
    # Aをi個、Bをj個選ぶ
    for i in range(n):
        for j in range(m)[::-1]:
            #print(i,j,X[i],Y[j])
            if X[i] + Y[j] <= k:
                cnt = max(cnt, i + j)
                break
    print(cnt)



if __name__ == "__main__":
    main()


### FIXED CODE ###

# from collections import deque
import numpy as np
def main():
    n, m, k = map(int, input().split())
    A = np.array([0] + list(map(int, input().split())))
    B = np.array([0] + list(map(int, input().split())))
    X = np.cumsum(A)
    Y = np.cumsum(B)
    # print(P,Q)

    cnt = 0
    j = m
    # Aをi個、Bをj個選ぶ
    for i, x in enumerate(X):
        if x > k:
            break

        while x + Y[j] > k:
            j -= 1
        cnt = max(cnt, i + j)

    print(cnt)

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

import math

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

n=0
z=[]
while(n<len(s)):
    x=[]
    for i in range(len(s)-n):
        x.append(s[i:i+n+1])
    y = sorted(list(set(x)))
    z += y[:5]
    n += 1
#print(z)
print(sorted(list(set(z)))[K-1])

### FIXED CODE ###


import math

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

init = sorted(set(list(s)))[:K]
n=0
z=[]
while(n<len(s)):
    if n > 500: break
    x=[]
    for i in range(len(s)-n):
        if s[i] in init:
            x.append(s[i:i+n+1])
    y = sorted(set(x+z))
    z = y[:K]
    n += 1
print(sorted(set(z))[K-1])
### BUGGY CODE ###

from sys import stdin

S = input()
Q = int(input())

for i in range(Q):
    tmp = list(input().split())
    if tmp[0] == '1':
        S = S[::-1]
    if tmp[0] == '2':
        F = tmp[1]
        C = tmp[2]
        if F == '1':
            S = C + S
        else:
            S = S + C

print(S)


### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())
s = deque(S)
reverse = True

for i in range(Q):
    tmp = list(input().split())
    if tmp[0] == '1':
        reverse = not reverse
    if tmp[0] == '2':
        F = tmp[1]
        C = tmp[2]
        if F == '1':
            if reverse:
                s.appendleft(C)
            else:
                s.append(C)
        else:
            if reverse:
                s.append(C)
            else:
                s.appendleft(C)
if reverse:
    print(''.join(s))
else:
    print(''.join(list(s)[::-1]))