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

s = input()
k = int(input())

substrings = set()
n = len(s)
for i in range(n):
  for j in range(i+1,n+1):    
    substrings.add(s[i:j])
    
print(sorted(substrings)[k-1])

### FIXED CODE ###

s = input()
k = int(input())

substrings = set()
n = len(s)
for i in range(n):
  for j in range(1,k+1):    
    substrings.add(s[i:i+j])
    
print(sorted(substrings)[k-1])
### BUGGY CODE ###

#C

n, k, q = map(int, input().split())
a=[]
for i in range(q):
    ak = int(input())
    a.append(ak)
#print(a)

seikai = []
for j in range(n):
    #プレイヤーjの正解数を調べる
    ss = a.count(j+1)
    ten = k - q + ss
#    print(ss)
    if ten > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

#C

n, k, q = map(int, input().split())
seikai=[0]*n
#seikai[i]はプレーヤーi+1の正解数
#print(seikai)
for i in range(q):
    ak = int(input())
    seikai[ak-1] += 1
#print(a)
#print(seikai)
for j in range(n):
    if seikai[j] > q-k:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n=int(input())
a = list(map(int, input().split()))
new=sorted(a,reverse=True)
ans=0
for i in range(0,n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if new[i]>=new[j]+new[k]:
                break
            else:
                ans+=1
print(ans)

### FIXED CODE ###

import bisect
n=int(input())
a = list(map(int, input().split()))
new=sorted(a)
ans=0
for i in range(0,n-2):
    for j in range(i+1,n-1):
        m=bisect.bisect_left(new,new[i]+new[j])
        ans+=(m-1)-j
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
numbers=[str(i).zfill(3) for i in range(1000)]
 
count=0
for num in numbers:
  j=0
  for i in range(N):
    if num[j]==S[i]:
      j+=1
      if j==3:
        count+=1
        break

print(count)

### FIXED CODE ###

N = int(input())
S = input()
numbers=[str(i).zfill(3) for i in range(1000)]
 
count=0
for num in numbers:
  j=0
  for i in range(N):
    if num[j]==S[i]:
      j+=1
      if j==3:
        count+=1
        break
print(count)
### BUGGY CODE ###

N, M = map(int, input().split())

f = [{} for i in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    f[a][b] = True
    f[b][a] = True

for i in range(N):
    koho = set()
    for k in f[i].keys():
        for ff in f[k].keys():
            if not(ff in f[i]):
                koho.add(ff)
    for k in koho:
        f[i][k] = True

ans = 0
zumi = set()
for i in range(N):
    if i in zumi:
        continue

    koho = set()
    ans += 1
    for j in range(N):
        if j in koho or j in zumi:
            continue
        for k in koho:
            if j in f[k]:
                break
        else:
            koho.add(j)
            zumi.add(j)
print(ans)


### FIXED CODE ###

import sys


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


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())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a, b)

ans = 0
for i in range(N):
    ans = max(ans, uf.size(i))
print(ans)
### BUGGY CODE ###

from math import sqrt
from itertools import product
import sys

n = int(input())
p = []
def factorization(arg):
    while arg % 2 == 0:
        p.append(2)
        arg //= 2
    for i in range(3, int(sqrt(arg)) + 1, 2):
        while arg % i == 0:
            p.append(i)
            arg //= i
    if arg > 1:
        p.append(arg)
if n == 1:
    print(1)
else:
    factorization(n)
    min = sys.maxsize
    for bit in range(2 ** len(p)):
        a = 1
        b = 1
        for i in range(len(p)):
            if ((bit >> i) & 1):
                a *= p[i]
            else:
                b *= p[i]
        if min > a and a >= b:
            min = a
        elif min > b and b > a:
            min = b
    print(len(str(min)))

### FIXED CODE ###

from math import sqrt
from itertools import product
import sys

n = int(input())
p = []
def factorization(arg):
    while arg % 2 == 0:
        p.append(2)
        arg //= 2
    for i in range(3, int(sqrt(arg)) + 1, 2):
        while arg % i == 0:
            p.append(i)
            arg //= i
    if arg > 1:
        p.append(arg)
if n == 1:
    print(1)
else:
    factorization(n)
    min = sys.maxsize
    for bit in range(2 ** len(p)):
        a = 1
        b = 1
        for i in range(len(p)):
            if ((bit >> i) & 1):
                a *= p[i]
            else:
                b *= p[i]
        if min > len(str(a)) if len(str(a)) >= len(str(b)) else len(str(b)):
            min = len(str(a)) if len(str(a)) >= len(str(b)) else len(str(b))
    print(min)
### BUGGY CODE ###

# coding=UTF-8
from collections import deque
from operator import itemgetter
from bisect import bisect_left, bisect
import itertools
import sys
import math
import numpy as np
import time
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


def main():
    n, x, y = map(int, input().split())
    tree = [[0] * n for i in range(n)]

    for i in range(1, n):
        for j in range(i+1, n+1):
            # if i <= x and j >= y:
            #     tree[i - 1][j - 1] = j-i-(y - x - 1)
            # elif i <= x and j < y:
            #     tree[i - 1][j - 1] = x - i + min(y - j + 1, j - x)
            # elif i > x and j >= y:
            #     tree[i - 1][j - 1] = j - y + min(i-x+1, y-i)
            # else:
            #     tree[i - 1][j - 1] = j-i
            tree[i - 1][j - 1] = min(j-i, abs(x-i) +
                                     1+abs(j-y), abs(y-i)+1+abs(j-x))

    for k in range(1, n):
        ans = 0
        for i in range(n):
            ans += tree[i].count(k)
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop
import copy
import numpy as np
import sys
INF = float('inf')
mod = 10**9+7


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

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def main():
    n, x, y = LI()
    d = [0]*n
    for i in range(1, n):
        for j in range(i + 1, n + 1):
            d[min(j - i, abs(x - i) + 1 + abs(j - y),
                  abs(y - i) + 1 + abs(j - x)) - 1] += 1
    for k in range(n-1):
        print(d[k])


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

n = int(input())
dic = {}

for i in range(n):
    dic[i+1] = int(input())
    
light = dic[1]
ans = 1

while light != 2:
    ans += 1
    light = dic[light]
    
    if light == 1:
        ans = -1
        break
    
print(ans)

### FIXED CODE ###

n = int(input())
dic = {i+1:int(input()) for i in range(n)}
light = dic[1]
ans = 1

for i in range(n):
    if light == 2:
        break
    elif light == 1 or i == n-1:
        ans = -1
        break
    else:
        ans += 1
        light = dic[light]
    
print(ans)
### BUGGY CODE ###

class Node:
    def __init__(self, x):
        self.data = x
        self.left = None
        self.right = None
        
def search_min(node):
    while node.left is not None:
        node = node.left
    return node.data

def insert(node, x):
    if node is None : return Node(x)
    elif x < node.data :
        node.left = insert(node.left, x)
    else :
        node.right = insert(node.right, x)
    return node

def delete_min(node):
    if node.left is None : return node.right
    node.left = delete_min(node.left)
    return node

def delete(node, x):
    if node is not None :
        if x == node.data :
            if node.left is None :
                return node.right
            elif node.right is None:
                return node.left
            else :
                node.data = search_min(node.right)
                node.right = delete_min(node.right)
        elif x < node.data :
            node.left = delete(node.left, x)
        else :
            node.right = delete(node.right, x)
    return node

[N,L] = [int(x) for x in input().split()]
A = [[int(x),int(i)] for i,x in enumerate(input().split())]
Tree = None
for i in range(L) : Tree = insert(Tree,A[i])
ANS = [search_min(Tree)[0]]

for i in range(L,N):
    Tree = delete(Tree, A[i-L])
    Tree = insert(Tree, A[i])
    ANS.append(search_min(Tree)[0])
    
for i in ANS[:-1]:
    print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

from operator import mul
from functools import reduce

N,M,K = map(int, input().split())
mod = 10**9+7
nm = N*M
n2 = (N**2)%mod
m2 = (M**2)%mod



def n_C_r(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

ans = 0
for x in range(1,M):
    ans += x*(M-x)*n2*n_C_r(nm-2,K-2)
    ans %= mod

for y in range(1,N):
    ans += y*(N-y)*m2*n_C_r(nm-2,K-2)
    ans %= mod

print(int(ans))

### FIXED CODE ###

N,M,K = map(int, input().split())
mod = 10**9+7
nm = N*M
n2 = (N**2)%mod
m2 = (M**2)%mod

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, 10**6 +1):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


ans = 0
for x in range(1,M):
    ans += x*(M-x)*n2*cmb(nm-2,K-2,mod)
    ans %= mod

for y in range(1,N):
    ans += y*(N-y)*m2*cmb(nm-2,K-2,mod)
    ans %= mod

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

k = int(input())
if k % 2 == 0:
  print(-1)
nana = 0
ans = 0
while True:
  nana += (10**ans) * 7
  #print(nana)
  if nana % k == 0:
    print(ans + 1)
    break
  ans += 1

### FIXED CODE ###

k = int(input())
if k % 2 == 0:
    print(-1)
elif k in [1,7]:
  	print(1)
else:
  amari = [7]
  tmp = 7
  for i in range(k):
      tmp = (tmp * 10) % k
      if tmp != 7:
          amari.append(tmp%k)
      else:
          break
  amari = amari * ((k//len(amari)) +1)

  ans = amari[0]
  for i in range(1, k+1):
      ans += amari[i]
      if ans % k == 0:
          print(i+1)
          break
  else:
    print(-1)
### BUGGY CODE ###

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

# 組み合わせをカウントする変数
count = 0

# 変数の初期化
x = 0
y = 0
z = 0

for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x + y + z == s:
                count += 1

print(count)


### FIXED CODE ###

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

# 組み合わせをカウントする変数
count = 0

# 変数の初期化
x = 0
y = 0
z = 0

for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if z >= 0 and z <= k:
            count += 1

print(count)
### BUGGY CODE ###

import sys

def main():
    l = input().split()
    a = int(l[0])
    b = int(l[1])

    if a > b:
        print("plz let 'a' smaller than 'b'")
        quit()

    temp = 1
    for i in range(a, b+1):
        temp *= i
    else:
        if temp == 0:
            print("Zero")
        elif temp > 0:
            print("Positive")
        else:
            print("Negative")


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def main():
    l = input().split()
    a = int(l[0])
    b = int(l[1])

    if a <= 0 and b >= 0:
        print("Zero")
    elif a > 0:
        print("Positive")
    elif b < 0:
        if (b - a) % 2 != 0:
            print("Positive")
        else:
            print("Negative")

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

K = int(input())

import itertools
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

lis = [i for i in range(1,K+1)]
S = [gcd_list(team) for team in itertools.product(lis, repeat = 3)]
print(sum(S))


### FIXED CODE ###

K = int(input())

import itertools
import math
from functools import reduce

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

lis = list(range(1,K+1))
S = [gcd_list(team) for team in itertools.product(lis, repeat = 3)]

print(sum(S))
### BUGGY CODE ###

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

import sys

N = int(input())
A = [input() for i in range(N)]

mx = 0
d = {}
r = []

for a in A:
    if not a in d:
        d[a] = 0
    d[a] += 1
    if d[a] > mx:
        r = [a]
        mx = d[a]
    elif d[a] == mx:
        if not a in r:
            r.append(a)
            r.sort()

for i in r:
    print(i)


### FIXED CODE ###

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

import sys

N = int(input())
A = [input() for i in range(N)]

mx = 0
d = {}
r = []

for a in A:
    if not a in d:
        d[a] = 0
    d[a] += 1
    if d[a] > mx:
        r = [a]
        mx = d[a]
    elif d[a] == mx:
        r.append(a)

r.sort()
for i in r:
    print(i)
### BUGGY CODE ###

# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    n = int(input())
    seq = [int(input()) for _ in range(n)]

    # リストseqからLISの長さを出す

    import bisect
    
    def main():
        cnt=0
        while len(seq)>0:

            LIS = [seq[0]]
            for i in range(len(seq)):
                if seq[i] > LIS[-1]:
                    LIS.append(seq[i])
                else:
                    LIS[bisect.bisect_left(LIS, seq[i])] = seq[i]
            cnt+=1
            
            for i in LIS:
                seq.remove(i)
        return cnt
    print(main())
    




resolve()

### FIXED CODE ###

# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import unittest
from io import StringIO
import sys
sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    n = int(input())
    seq = [int(input()) for _ in range(n)][::-1]

    """
    Longest Increasing/Decreasing Subsuquence (LIS, LDS)
    Verified:
        https://atcoder.jp/contests/abc134/tasks/abc134_e
        https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_1_D
    """


    def longest_subsequence(A: "Array[int]", equals: bool, increasing: bool) -> int:
        """
        Compute the length of LIS or LDS.
        
        Args:
            A ("Array[int]"): a list or tuple to compute.
            equals (bool): permit adjacent numbers in subsequence to equal.
            increasing (bool): compute an increasing subsequence or decreasing one.
        Returns: (int) the length of a subsequence.
        """
        from bisect import bisect_left, bisect_right

        bs = bisect_right if equals else bisect_left
        compare = (lambda x, y: x >= y) if equals else (lambda x, y: x > y)
        if not increasing:
            A = A[::-1]

        dp = [A[0]]  # dp := length of LIS (dp table itself is not LIS)
        for i in A[1:]:
            if compare(i, dp[-1]):
                dp.append(i)
            else:
                dp[bs(dp, i)] = i
        return len(dp)
    
    print(longest_subsequence(seq,True,True))

    
    




resolve()
### BUGGY CODE ###

import sys

N,K=list(map(int,input().split()))
h=list(map(int,input().split()))+[0]*100000

dp=[sys.maxsize]*(N+K+10)
dp[1]=0

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

print(dp[N])

### FIXED CODE ###

import sys
import numpy as np
# inputを高速化する。
input = sys.stdin.readline
n, k = map(int, input().split())
h = [int(i) for i in input().split()]
# dpの配列を作る。
dp = np.zeros(n, dtype=int)
# hの配列を作る。
h = np.array(h)
for i in range(1, n):
    # start は負になることはない。
    start = max(0, i-k)
    # 行列として足し算できるのでforを使う必要がない。
    dp[i] = min(dp[start: i] + np.abs(h[i] - h[start: i]))
print(dp[n-1])
### BUGGY CODE ###

N,M = map(int,input().split(" "))
first = []
second = []
flag = 0

for i in range(M):
  a,b = map(int,input().split(" "))
  if b == N:
    second.append([a,b])
  if a == 1:
    first.append([a,b])
    
if len(first) == 0 or len(second) == 0:
  print("IMPOSSIBLE")
else:
  for j in range(len(first)):
    for k in range(len(second)):
      if first[j][1] == second[k][0]:
        print("POSSIBLE")
        flag = 1
        break
  if flag == 0:
    print("IMPOSSIBLE")

### FIXED CODE ###

N,M = map(int,input().split(" "))

first = []
second = []
flag = 0
end = True

for i in range(M):
  a,b = map(int,input().split(" "))
  if b == N:
    second.append(a)
  if a == 1:
    first.append(b)

first.sort()
second.sort()
    
if len(first) == 0 or len(second) == 0:
  print("IMPOSSIBLE")
else:
  firsti = 0
  secondi = 0
  while(end == True):
    if first[firsti] == second[secondi]:
      print("POSSIBLE")
      break
    elif first[firsti] < second[secondi]:
      firsti += 1
      if firsti > len(first) - 1:
        print("IMPOSSIBLE")
        break
    else:
      secondi += 1
      if secondi > len(second) - 1:
        print("IMPOSSIBLE")
        break
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
ans = 0
for i in range(N):
  for j in range(i+1, N):
    for k in range(j+1, N):
      A = L[i] + L[j] + L[k]
      if(max(L[i],  L[j],  L[k]) < (A - max(L[i],  L[j],  L[k]))):
        ans += 1
        
print(ans)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N):
  for j in range(i+1, N):
    A = L[i] + L[j]
    highbound = bisect_left(L, A)
    ans += highbound - j - 1    
print(ans)
### BUGGY CODE ###

from itertools import product

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 = sorted([s+t for s,t in product(a,b)], reverse=True)[:3000]
e = sorted([s+t for s,t in product(c,d)], reverse=True)[:k]
[print(i) for i in e]


### FIXED CODE ###

*xyz,k = map(int, input().split()) 
xyz_list = []
xyz_list.append(list(map(int, input().split())))
xyz_list.append(list(map(int, input().split())))
xyz_list.append(list(map(int, input().split())))
xyz_list[0].sort(reverse=True)
xyz_list[1].sort(reverse=True)
xyz_list[2].sort(reverse=True)

print(xyz_list[0][0]+xyz_list[1][0]+xyz_list[2][0])
p = [1,0,0]
num = lambda x: [
    [x[0]+p[i], x[1]+p[(4-i)%3], x[2]+p[(5-i)%3],
    xyz_list[0][x[0]+p[i]]+xyz_list[1][x[1]+p[(4-i)%3]]+xyz_list[2][x[2]++p[(5-i)%3]]]
    for i in range(3) if x[i]+1 < xyz[i]]
stack = num([0,0,0])
num_dict={}
for i in stack:
    if i[3] not in num_dict:
        num_dict[i[3]] = [[i[0], i[1], i[2]]]
    else:
        num_dict[i[3]].append([i[0], i[1], i[2]])
k -= 1
while k != 0:
    x, y, z, maxi = max(stack, key=lambda x:x[3])
    print(maxi)
    k -= 1
    if k == 0:
      break
    stack.remove([x,y,z,maxi])
    for i in num([x,y,z]):
        if i[3] not in num_dict:
            num_dict[i[3]] = [[i[0], i[1], i[2]]]
            stack.append([i[0], i[1], i[2], i[3]])
        elif [i[0], i[1], i[2]] not in num_dict[i[3]]:
            num_dict[i[3]].append([i[0], i[1], i[2]])
            stack.append([i[0], i[1], i[2], i[3]])
### BUGGY CODE ###

dict = {}
for i in range(int(input())):
    a = input()
    if dict.get(a):
        dict[a] += 1
    else:
        dict[a] = 1



ans = [key for key, value in dict.items() if value == max(dict.values())]
ans.sort()
for i in ans:
    print(i)


### FIXED CODE ###

dict = {}
for i in range(int(input())):
    a = input()
    if dict.get(a):
        dict[a] += 1
    else:
        dict[a] = 1

max_v = max(dict.values())


ans = [key for key, value in dict.items() if value == max_v]
ans.sort()
for i in ans:
    print(i)
### BUGGY CODE ###

S=input()
Q=int(input())
list=[]
mojiretu=[z for z in S]
for a in range(Q):
    b=input().split()
    list.append(b)
for c in list:
    if len(c)==1:
        mojiretu.reverse()
    else:
        if c[1]=='1':
            mojiretu.insert(0,c[2])
        else:
            mojiretu.append(c[2])
print(''.join(mojiretu))


### FIXED CODE ###

from collections import deque
S=input()
Q=int(input())
words=[]
for a in range(Q):
    A=input().split()
    words.append(A)
T=[a for a in S]
answers=deque(T)
number=0
for a in words:
    if a[0]=='1':
        number+=1
    else:
        if number%2==0:
            if a[1]=='1':
                answers.appendleft(a[2])
            else:
                answers.append(a[2])
        else:
            if a[1]=='1':
                answers.append(a[2])
            else:
                answers.appendleft(a[2])
if number%2==0:
    kotae=list(answers)
    moji=''
    for a in kotae:
        moji+=a
    print(moji)
else:
    kotae = list(answers)
    kotae.reverse()
    moji = ''
    for a in kotae:
        moji += a
    print(moji)