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

MOD = 10**9+7
n = int(input())
S = input()
dp = [[0]*(n+1) for _ in range(n+1)]
for j in range(n):
  dp[1][j] = 1
for i, s in enumerate(S, 1):
  if s == "<":
    dp[i+1][n-(i+1)] = dp[i][n-i]
    for j in range(n-i-2, -1, -1):
      dp[i+1][j] = dp[i+1][j+1] + dp[i][j+1]
      dp[i+1][j] %= MOD
  else:
    dp[i+1][0] = dp[i][0]
    for j in range(1, n-i):
      dp[i+1][j] = dp[i+1][j-1] + dp[i][j]
      dp[i+1][j] %= MOD
ans = dp[n][0]
print(ans)

### FIXED CODE ###

MOD = 10**9+7
n = int(input())
S = input()
dp = [[0]*(n+1) for _ in range(n+1)]
for j in range(n):
  dp[1][j] = 1
for i, s in enumerate(S, 1):
  if s == "<":
    dp[i+1][n-(i+1)] = dp[i][n-i]
    for j in range(n-i-2, -1, -1):
      dp[i+1][j] = dp[i+1][j+1] + dp[i][j+1]
      dp[i+1][j] %= MOD
  else:
    dp[i+1][0] = dp[i][0]
    for j in range(1, n-i):
      dp[i+1][j] = dp[i+1][j-1] + dp[i][j]
      dp[i+1][j] %= MOD
ans = dp[n][0]
print(ans)
### BUGGY CODE ###

from scipy.sparse.csgraph import floyd_warshall


def main():
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    wf = floyd_warshall(A)
    edges = list()
    for i in range(N):
        for j in range(i + 1, N):
            edges.append((A[i][j], i, j))  # (cost, from, to)
    edges.sort()
    ans = 0
    for edge in edges:
        cost, from_node, to_node = edge
        if A[from_node][to_node] > wf[from_node][to_node]:
            print(-1)
            return
        to_be_added = True
        for via_node in range(N):
            if via_node in [from_node, to_node]:
                continue
            if wf[from_node][to_node] == wf[from_node][via_node] + wf[via_node][to_node]:
                to_be_added = False
                break
        if to_be_added:
            ans += A[from_node][to_node]
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

from scipy.sparse.csgraph import floyd_warshall
import numpy as np


def main():
    INF = 10**12
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    wf = floyd_warshall(A)
    for i in range(N):
        A[i][i] = INF
        wf[i][i] = INF
    ans = 0
    for i in range(N):
        for j in range(N):
            if A[i][j] != wf[i][j]:
                print(-1)
                return
            if wf[i][j] < np.min(wf[i] + wf[j]):
                ans += wf[i][j]
    print(int(ans // 2))


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

N,K = [int(x) for x in input().split()]
H = [int(x) for x in input().split()]

INF = 10**9
dp = [INF] * N
dp[0] = 0

for i in range(0, N - 1):
    for k in range(0, min(i + 1, K)):
        if dp[i + 1] > dp[i - k] + abs(H[i + 1] - H[i - k]):
            dp[i + 1] = dp[i - k] + abs(H[i + 1] - H[i - k])

print(dp[N-1])

### FIXED CODE ###

N,K = [int(x) for x in input().split()]
H = [int(x) for x in input().split()]

INF = 10**9
dp = [INF] * N
dp[0] = 0

for i in range(0, N - 1):
    for k in range(0, min(i + 1, K)):
        if dp[i + 1] > dp[i - k] + abs(H[i + 1] - H[i - k]):
            dp[i + 1] = dp[i - k] + abs(H[i + 1] - H[i - k])


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

import bisect
 
 
class SegTree:
 
    def __init__(self, n):
        # supposed that n = 2**m
        self.n = n
        self.val = [-1] * (2 * n - 1)
 
    def _update(self, a, b, v, k, l, r):
        if r <= a or b <= l:
            return
        if a <= l and r <= b:
            self.val[k] = v
        else:
            self._update(a, b, v, 2 * k + 1, l, (l + r) // 2)
            self._update(a, b, v, 2 * k + 2, (l + r) // 2, r)
 
    def update(self, a, b, v):
        # 区間[a, b)上の値をvに更新
        self._update(a, b, v, 0, 0, self.n)
 
    def query(self, x):
        # ノードxの値を返す
        k = self.n + x - 1
        ret = self.val[k]
        while k > 0:
            k = (k - 1) // 2
            ret = max(ret, self.val[k])
        return ret
 
 
def main():
    N, Q = list(map(int, input().split(' ')))
    work_list = [0] * N
    for n in range(N):
        work_list[n] = list(map(int, input().split(' ')))
    # 工事は出発地から遠い順に並べておく
    work_list.sort(key=lambda work: work[2], reverse=True)
    D = [0] * Q
    for q in range(Q):
        D[q] = int(input())
    # 一番最初に引っかかる工事のインデックスを求める
    QQ = 1
    while QQ < Q:
        QQ <<= 1
    tree = SegTree(QQ)
    for w, work in enumerate(work_list):
        s, t, x = work
        # s - x <= d < t - x だと工事に引っかかる
        left = bisect.bisect_left(D, s - x)
        right = bisect.bisect_left(D, t - x)
        tree.update(left, right, w)
    for q in range(Q):
        w = tree.query(q)
        if w == -1:
            print(-1)
        else:
            print(work_list[w][2])
 
 
if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect
 
 
class SegTree:
 
    def __init__(self, n):
        # supposed that n = 2**m
        self.n = n
        self.val = [-1] * (2 * n - 1)
 
    def _update(self, a, b, v, k, l, r):
        # 区間[a, b)上の値をvに更新
        if r <= a or b <= l:
            return
        if a <= l and r <= b:
            self.val[k] = v
        else:
            self._update(a, b, v, 2 * k + 1, l, (l + r) // 2)
            self._update(a, b, v, 2 * k + 2, (l + r) // 2, r)
 
    def query(self, x):
        # ノードxの値を返す
        k = self.n + x - 1
        ret = self.val[k]
        while k > 0:
            k = (k - 1) // 2
            ret = max(ret, self.val[k])
        return ret
 
 
def main():
    N, Q = list(map(int, input().split(' ')))
    work_list = [list(map(int, input().split(' '))) for n in range(N)] 
    # 工事は出発地から遠い順に並べておく
    work_list.sort(key=lambda work: work[2], reverse=True)
    D = [int(input()) for q in range(Q)]
    # 一番最初に引っかかる工事のインデックスを求める
    QQ = 1
    while QQ < Q:
        QQ <<= 1
    tree = SegTree(QQ)
    for w, work in enumerate(work_list):
        s, t, x = work
        # s - x <= d < t - x だと工事に引っかかる
        left = bisect.bisect_left(D, s - x)
        right = bisect.bisect_left(D, t - x)
        tree._update(left, right, w, 0, 0, QQ)
    for q in range(Q):
        w = tree.query(q)
        if w == -1:
            print(-1)
        else:
            print(work_list[w][2])
 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

INF = 10**10 - 1 #無限大
SMAX = 3000 + 1

# 文字列入力
s1 = input()
s2 = input()

'''
dpの初期化
s1の文字列位置を一次軸、s2の文字列位置を二次軸に取り
その値として：LCSの最長値として更新していく
　　　　　　　初期値はすべて０
'''
dp = [ [0] * (len(s2)+1) for i in range(len(s2)+1)]

for s1pos in range(1,len(s1)+1):
    s1s = s1[s1pos-1:s1pos]
    for s2pos in range(1,len(s2)+1):
        s2s = s2[s2pos-1:s2pos]
        if s1s == s2s:
            dp[s1pos][s2pos] = dp[s1pos-1][s2pos-1] + 1
        dp[s1pos][s2pos] = max(dp[s1pos][s2pos],dp[s1pos][s2pos-1],dp[s1pos-1][s2pos])
    #print("s1pos=",s1pos,"dp=",dp[s1pos])

#print("LCS_len",dp[len(s1)][len(s2)])

res = ""
s1pos = len(s1)
s2pos = len(s2)
while (s1pos > 0 and s2pos > 0):
    # (s1pos-1, s2pos) -> (s1pos, s2pos) と更新されていた場合
    if (dp[s1pos][s2pos] == dp[s1pos-1][s2pos]):
        s1pos -= 1 # DP の遷移を遡る
    # (s1pos, s2pos-1) -> (s1pos, s2pos) と更新されていた場合
    elif (dp[s1pos][s2pos] == dp[s1pos][s2pos-1]):
        s2pos -= 1 # DP の遷移を遡る
    # (s1pos-1, s2pos-1) -> (s1pos, s2pos) と更新されていた場合
    else:
        res = s1[s1pos-1:s1pos] + res # 該当文字を取得
        s1pos -= 1 # DP の遷移を遡る
        s2pos -= 1 # DP の遷移を遡る

print(res)

### FIXED CODE ###

INF = 10**10 - 1 #無限大
SMAX = 3000 + 10

# 文字列入力
s1 = input()
s2 = input()

'''
dpの初期化
s1の文字列位置を一次軸、s2の文字列位置を二次軸に取り
その値として：LCSの最長値として更新していく
　　　　　　　初期値はすべて０
'''
dp = [ [0] * (SMAX) for i in range(SMAX)]

for s1pos in range(1,len(s1)+1):
    s1s = s1[s1pos-1:s1pos]
    for s2pos in range(1,len(s2)+1):
        s2s = s2[s2pos-1:s2pos]
        if s1s == s2s:
            dp[s1pos][s2pos] = dp[s1pos-1][s2pos-1] + 1
        dp[s1pos][s2pos] = max(dp[s1pos][s2pos],dp[s1pos][s2pos-1],dp[s1pos-1][s2pos])
    #print("s1pos=",s1pos,"dp=",dp[s1pos])

#print("LCS_len",dp[len(s1)][len(s2)])

res = ""
s1pos = len(s1)
s2pos = len(s2)
while (s1pos > 0 and s2pos > 0):
    # (s1pos-1, s2pos) -> (s1pos, s2pos) と更新されていた場合
    if (dp[s1pos][s2pos] == dp[s1pos-1][s2pos]):
        s1pos -= 1 # DP の遷移を遡る
    # (s1pos, s2pos-1) -> (s1pos, s2pos) と更新されていた場合
    elif (dp[s1pos][s2pos] == dp[s1pos][s2pos-1]):
        s2pos -= 1 # DP の遷移を遡る
    # (s1pos-1, s2pos-1) -> (s1pos, s2pos) と更新されていた場合
    else:
        res = s1[s1pos-1:s1pos] + res # 該当文字を取得
        s1pos -= 1 # DP の遷移を遡る
        s2pos -= 1 # DP の遷移を遡る

print(res)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
input=sys.stdin.readline


def main():
    N, S = map(int, input().split())
    *A, = map(int, input().split())
    dp = [[0]*(3001) for _ in range(N+1)]
    MOD = 998244353
    ans = 0

    dp[0][0] = pow(2, N, MOD)
    for i in range(1, N+1):    
        for j in range(3001):
            dp[i][j] += dp[i-1][j]
            if j-A[i-1]>=0:
                dp[i][j] += dp[i-1][j-A[i-1]]*pow(2, MOD-2, MOD)
            dp[i][j] %= MOD

    print(dp[N][S])


main()

### FIXED CODE ###

import sys
input=sys.stdin.readline


def main():
    N, S = map(int, input().split())
    *A, = map(int, input().split())
    dp = [[0]*(3001) for _ in range(N+1)]
    MOD = 998244353
    m = pow(2, MOD-2, MOD)
    dp[0][0] = pow(2, N, MOD)
    for i in range(1, N+1):    
        for j in range(3001):
            dp[i][j] += dp[i-1][j]
            if j-A[i-1]>=0:
                dp[i][j] += dp[i-1][j-A[i-1]]*m
            dp[i][j] %= MOD

    print(dp[N][S])


main()
### BUGGY CODE ###

import sys

import numpy as np

readline = sys.stdin.buffer.readline


# 同じ数値が複数あるとおかしくなる
def binary_search(A, n, p):
    if p == "+":
        n += 0.5
    else:
        n -= 0.5

    left = 0
    right = len(A) - 1

    if n < A[0]:
        return 0
    else:
        while left <= right:
            mid = (left + right) // 2
            if A[mid] < n:
                left = mid + 1
            else:
                right = mid - 1

        return left


def main():
    N = int(readline())
    A = np.array(list(map(int, readline().split())))
    B = np.array(list(map(int, readline().split())))
    C = np.array(list(map(int, readline().split())))

    A, B, C = np.sort(A), np.sort(B), np.sort(C)

    ab = np.zeros([N], dtype=np.int32)
    for i, b in enumerate(B):
        ab[i] = binary_search(A, b, "-")

    bc = np.zeros([N], dtype=np.int32)
    for i, b in enumerate(B):
        bc[i] = -binary_search(C, b, "+") + N

    cnt = 0
    for i, j in zip(ab, bc):
        cnt += i * j
    print(cnt)


main()


### FIXED CODE ###

import sys

readline = sys.stdin.buffer.readline


def binary_search(A, n, p):
    if p == "+":
        n += 0.5
    else:
        n -= 0.5

    left = 0
    right = len(A) - 1

    if n < A[0]:
        return 0
    else:
        while left <= right:
            mid = (left + right) // 2
            if A[mid] < n:
                left = mid + 1
            else:
                right = mid - 1

        return left


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    B = list(map(int, readline().split()))
    C = list(map(int, readline().split()))

    A, B, C = sorted(A), sorted(B), sorted(C)

    cnt = 0
    for i, b in enumerate(B):
        ab = binary_search(A, b, "-")
        bc = N - binary_search(C, b, "+")
        cnt += ab * bc

    print(cnt)


main()
### BUGGY CODE ###

import math
K = int(input())
 
c = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for l in range(1,K+1):
            a = math.gcd(math.gcd(i,j), l)
            c += a
 
print(c)

### FIXED CODE ###

from math import gcd
ans = 0
n = int(input())

for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            l = gcd(i,j)
            ans += gcd(k,l)
print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
ls = list(map(int, input().split()))

ans = 0

for i in range(n - k + 1):
    exv = 0
    for j in range(k):
        exv += (ls[i + j] + 1) / 2
    
    if exv > ans:
        ans = exv

print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
ls = list(map(int, input().split()))

exv = 0

for j in range(k):
    exv += (ls[j] + 1) / 2

ans = exv

for i in range(k, n):
    exv += (ls[i] + 1) / 2
    exv -= (ls[i - k] + 1) / 2
    
    if exv > ans:
        ans = exv

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

import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    S = input()
    slen = len(S)
    ans = 0
    for i in range(0, slen):
        start = i
        end = i + 4
        while end <= slen:
            if (int(S[start:end])) % 2019 == 0:
                start = end + 1
                end = start + 4
                ans += 1
            else:
                end += 1
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    S = input()
    s_list = list(map(int, list(S)))[::-1]
    MOD = 2019

    sum_v = 0
    cnt = [0] * MOD
    cnt[0] = 1
    for i, s in enumerate(s_list):
        sum_v += s * pow(10, i, MOD)
        sum_v %= MOD
        cnt[sum_v] += 1
    print(sum([c * (c - 1) // 2 for c in cnt if c > 1]))

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

from itertools import combinations
from bisect import bisect_left, bisect_right

N = int(input()) #2*10**3
L_list = [int(e) for e in input().split()]
index_list = [i for i in range(N)]

L_list.sort(reverse=False)
#print(L_list)

ans = 0

for i in range(0,N-1):
    for j in range(i+1,N):
        a = L_list[i]
        b = L_list[j]
        
        #a < b+c ∴a-b < c
        #b < c+a ∴b-a < c
        if a-b > 0:
            low_limit = a-b
        else:
            low_limit = b-a
        index_left = bisect_right(L_list, low_limit) #log(2*10**6)≒6.3

        #c < a+b
        index_right = bisect_left(L_list, a+b) #log(2*10**6)
        
        #print(a,b,low_limit,a+b)
        #print(L_list[index_left:index_right])
        
        OK_c = index_right - index_left
        
        if index_left <= i <= index_right:
            OK_c -= 1
        if index_left <= j <= index_right:
            OK_c -= 1
            
        #print(OK_c)
        ans += OK_c
    
print(ans//3)

### FIXED CODE ###

from itertools import combinations
from bisect import bisect_left, bisect_right

N = int(input()) #2*10**3
L_list = [int(e) for e in input().split()]
index_list = [i for i in range(N)]

L_list.sort(reverse=False)
#print(L_list)

ans = 0

for comb in combinations(index_list, 2): #(2*10*3)*(2*10*3 -1)/2 ≒ 2*10*6
    a = L_list[comb[0]]
    b = L_list[comb[1]]
    
    #a < b+c ∴a-b < c
    #b < c+a ∴b-a < c
    if a-b > 0:
        low_limit = a-b
    else:
        low_limit = b-a
    index_left = bisect_right(L_list, low_limit) #log(2*10**6)≒6.3

    #c < a+b
    index_right = bisect_left(L_list, a+b) #log(2*10**6)
    
    #print(a,b,low_limit,a+b)
    #print(L_list[index_left:index_right])
    
    OK_c = index_right - index_left
    
    if index_left <= comb[0] <= index_right:
        OK_c -= 1
    if index_left <= comb[1] <= index_right:
        OK_c -= 1
        
    #print(OK_c)
    ans += OK_c
    
print(ans//3)
### BUGGY CODE ###

from collections import deque
from itertools import islice
alfabet=deque(input())
n=int(input())
for i in range(n):
  operation_list=list(input().split())
  if int(operation_list[0])==1:
    alfabet2=list(alfabet)
    alfabet=deque(alfabet2[::-1])
  else:
    if int(operation_list[1])==2:
      alfabet.append(operation_list[2])
    else:
      alfabet.appendleft(operation_list[2])
print(''.join(alfabet))   

### FIXED CODE ###

from collections import deque
alfabet=deque(input())
n=int(input())
reverse=0
for i in range(n):
  operation_list=list(input().split())
  if int(operation_list[0])==1:
    reverse+=1
  else:
    if int(operation_list[1])==2 and reverse%2==0:
      alfabet.append(operation_list[2])
    elif int(operation_list[1])==2 and reverse%2==1:
      alfabet.appendleft(operation_list[2])
    elif int(operation_list[1])==1 and reverse%2==0:
      alfabet.appendleft(operation_list[2])
    elif int(operation_list[1])==1 and reverse%2==1:
      alfabet.append(operation_list[2])
if reverse%2!=0:
  alfabet.reverse()
print(''.join(alfabet))
### BUGGY CODE ###

N,Q = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(N - 1)]
px = [list(map(int,input().split())) for _ in range(Q)]
ab.sort()
px.sort()

plus = [0 for _ in range(N)]

for p,x in px:
        plus[p - 1] += x 

for a,b in ab:
        plus[b - 1] += plus[a - 1]
for p in plus:
        print(p)

### FIXED CODE ###

def main():
        N,Q = map(int,input().split())
        ab = [list(map(int,input().split())) for _ in range(N - 1)]
        px = [list(map(int,input().split())) for _ in range(Q)]
        ab.sort()
        # px.sort()
        plus = [0 for _ in range(N)]

        for p,x in px:
                plus[p - 1] += x 

        for a,b in ab:
                plus[b - 1] += plus[a - 1]
        for p in plus:
                print(p)

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

a,b,n=map(int,input().split())
res=0
x=n
for x in range(min(b,n+1)):
    res=max(res,int(a*x/b)-a*int(x/b))
print(res)

### FIXED CODE ###

a,b,n=map(int,input().split())
x=min(b-1,n)
max_res=int(a*x/b)-a*int(x/b)
print(max_res)
### BUGGY CODE ###

import re
N = int(input())
S = input()

ok, ng = 0, N + 1
while abs(ok - ng) > 1:
    x = (ok + ng) // 2
    for i in range(N - x + 1):
        target = S[i: i + x]
        regex = re.compile('{}.*{}'.format(target, target))
        mo = regex.search(S)
        if mo:
            ok = x
            break
    else:
        ng = x

print(ok)


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    ok, ng = 0, N + 1
    while abs(ok - ng) > 1:
        x = (ok + ng) // 2
        check = set()
        for i in range(N - x + 1):
            check.add(S[i: i + x])
            if S[i + x: i + 2 * x] in check:
                ok = x
                break
        else:
            ng = x

    print(ok)


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

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def main():
    n, m = map(int, sys.stdin.readline().split())
    lrds = tuple(tuple(map(int, line.split())) for line in sys.stdin.readlines())

    g = tuple([] for _ in range(n))
    x = [None] * n

    for l, r, d in lrds:
        l -= 1
        r -= 1
        g[l].append((r, d))
        g[r].append((l, -d))

    for i in range(n):
        if x[i]:
            continue
        stack = [i]
        x[i] = 0
        while len(stack):
            v = stack.pop()
            for u, d in g[v]:
                if not x[u]:
                    stack.append(u)
                    x[u] = x[v] + d

    for v in range(n):
        for u, d in g[v]:
            if x[v] + d != x[u]:
                print('No')
                sys.exit()

    print('Yes')

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def main():
    n, m = map(int, sys.stdin.readline().split())
    lrds = ((map(int, line.split())) for line in sys.stdin.readlines())

    g = tuple([] for _ in range(n))
    x = [None] * n

    for l, r, d in lrds:
        l -= 1
        r -= 1
        g[l].append((r, d))
        g[r].append((l, -d))

    for i in range(n):
        if x[i] is not None:
            continue
        stack = [i]
        x[i] = 0
        while len(stack):
            v = stack.pop()
            for u, d in g[v]:
                if x[u] is None:
                    stack.append(u)
                    x[u] = x[v] + d

    for v in range(n):
        for u, d in g[v]:
            if x[v] + d != x[u]:
                print('No')
                sys.exit()

    print('Yes')

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

N, M = [int(i) for i in input().split()]
Groups = [[i] for i in range(N)]
dsts = [-1 for i in range(N)]
ABs = [[int(i)-1 for i in input().split()] for i in range(M)]
for A, B in ABs:
    dst = min(A, B)
    src = max(A, B)
    # print('A', A, B, dst, src)
    while(dsts[dst] != -1):
        dst = dsts[dst]
    while(dsts[src] != -1):
        src = dsts[src]
    if dst == src:
        continue
    dst2 = min(dst, src)
    src2 = max(dst, src)
    dsts[src2] = dst2
    Groups[dst2].extend(Groups[src2])
    Groups[src2] = []
    # print(Groups)
    # print(dsts)
ans = 0
for group in Groups:
    ans = max(ans, len(group))
print(ans)


### FIXED CODE ###

N, M = [int(i) for i in input().split()]
Groups = [1 for i in range(N)]
dsts = [-1 for i in range(N)]
ABs = [[int(i)-1 for i in input().split()] for i in range(M)]
for A, B in ABs:
    dst = min(A, B)
    src = max(A, B)
    # print('A', A, B, dst, src)
    while(dsts[dst] != -1):
        dst = dsts[dst]
    while(dsts[src] != -1):
        src = dsts[src]
    if dst != min(A, B):
        omdst = min(A, B)
        while(dsts[omdst] != dst):
            n_omdst = dsts[omdst]
            dsts[omdst] = dst
            omdst = n_omdst
    if src != max(A, B):
        omsrc = max(A, B)
        while(dsts[omsrc] != src):
            n_omsrc = dsts[omsrc]
            dsts[omsrc] = src
            omsrc = n_omsrc

    if dst == src:
        continue
    dst2 = min(dst, src)
    src2 = max(dst, src)
    dsts[src2] = dst2
    Groups[dst2] += Groups[src2]
    Groups[src2] = 0
    # print(Groups)
    # print(dsts)
print(max(Groups))
### BUGGY CODE ###

S=input()
for i in range(int(input())):
    q=input()
    if q=='1':
        S=S[::-1]
    else:
        a,f,c=q.split()
        S=''.join((c,S)) if f=='1' else ''.join((S,c)) 
print(S)

### FIXED CODE ###

S=input()
b=1
x=''
y=''
for i in range(int(input())):
    q=input()
    if q=='1':b^=1
    else:
        a,f,c=q.split()
        if (int(f)-1)^b:x=c+x
        else:y=y+c
S=x+S+y
print(S if b else S[::-1])
### BUGGY CODE ###

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


def sort_here(ll):  # バブルソート
    for m in range(len(ll)):
        for n in range(len(ll)-1-m):
            A, B = compare(ll[n], ll[n+1])
            ll[n] = A
            ll[n + 1] = B
    return ll


def compare_(A, B):
    # このゲームにおける比較
    # 小、大の順で返す
    a = len(A)
    b = len(B)

    if a > b:
        if A[:b] == B:
            return B, A
    elif b > a:
        if B[:a] == A:
            return A, B

    for i in range(len(min(A, B))):
        if A[i] > B[i]:
            return B, A
        elif A[i] < B[i]:
            return A, B

def compare(A, B):
    # このゲームにおける比較
    # 小、大の順で返す
    for i in range(len(min(A, B))):
        if A[i] > B[i]:
            return B, A
        elif A[i] < B[i]:
            return A, B

    if len(A) < len(B):
        return A, B
    elif len(B) < len(A):
        return B, A
    else:
        raise Exception


# まずはありうるsubstringを準備
i_list = []
for i in range(1, len(s) + 1):
    # i文字数のsutringをまずは作る
    for j in range(len(s) - i + 1):
        cand = s[j:j+i]
        if cand not in i_list:
            i_list.append(s[j:j+i])

#print(i_list)

# 並び替え
i_list = sort_here(i_list)
#print(i_list)


# 出力
print(i_list[K-1])








### FIXED CODE ###

s = input()
l = len(s)
k = int(input())


def compare(a, b):
    ll = [a, b]
    ll = sorted(ll)
    return ll[0] == a


db = []
for length in range(1, k + 1):
    for start in range(l + 1 - length):
        candidate = s[start:start+length]
        if len(db) >= 5:
            if compare(candidate, db[-1]):
                if candidate not in db:
                    db.append(candidate)
                    db = sorted(db)
                    db = db[:5]
        else:
            if candidate not in db:
                db.append(candidate)
                db = sorted(db)

print(sorted(db)[k-1])