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

if __name__ == '__main__':
    text = input()
    number = int(input())
    dic = []

    for ss_len in range(1, len(text) + 1):
        for ss in range(0, len(text) - ss_len + 1):
            c = text[ss:ss_len + ss]
            if c not in dic:
                dic.append(c)

    dic = sorted(dic)

    print(dic[number - 1])

### FIXED CODE ###

if __name__ == '__main__':
    text = input()
    number = int(input())
    dic = []

    for text_len in range(1, min(len(text),number) + 1):
        for ss_len in range(0, len(text) - text_len + 1):
            word = text[ss_len:text_len + ss_len]
            if word not in dic:
                dic.append(word)

    dic = sorted(dic)

    print(dic[number - 1])
### BUGGY CODE ###

import sys
from collections import deque

V = list(input())
S = deque()
S.extend(V)
Q = int(input())

r = 0
for i in range(Q):
    c = sys.stdin.readline().split()
    
    #print('s:', S)
    #print('c:', c)

    if c[0] == '1':
        if r == 0: r+= 1
        else: r -= 1
        continue

    else:            
        if r == 1:
            S.reverse()
            r -= 1

        if c[1] == '1':
            S.appendleft(c[2])
        else:
            S.append(c[2])

if r == 1:
    S.reverse()

print(''.join(S))

### FIXED CODE ###

import sys
from collections import deque

V = list(input())
S = deque()
S.extend(V)
Q = int(input())

memo = []
r = 0
for i in range(Q):
    c = sys.stdin.readline().split()
    #print(c)
    if c[0] == '1':
        r += 1
        continue
    else:
        if c[1] == '1':
            memo.append((r, c[2]))
        else:
            memo.append((r+1, c[2]))
        
#print(memo)        
if r % 2 == 1:
    S.reverse()

for m in memo:
    s, l = m
    s = r - s
    if s % 2 == 0:
        S.appendleft(l)
    else:
        S.append(l)    

print(''.join(S))
### BUGGY CODE ###

import sys

n = input()
arr = [_.replace('\n', '') for _ in sys.stdin]
dic = {}
for s in arr:
  if s in dic.keys():
    dic[s] += 1
  else:
    dic[s] = 1
s = [k for k,v in dic.items() if v == max(dic.values())]
for i in sorted(s):
  print(i)

### FIXED CODE ###

import sys
import collections

n = input()
arr = [_.replace('\n', '') for _ in sys.stdin]
dic = collections.Counter(arr)
cnt = list(dic.values()).count(max(dic.values()))
s = [k for k,v in dic.most_common(cnt)]

for i in sorted(s):
  print(i)
### BUGGY CODE ###

n = int(input())

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

for i in range(1, n + 1):
  print(a.count(i))
  [n for n in a if n!= i ]

### FIXED CODE ###

n = int(input())

a = list(map(int,input().split()))
 
res = [0] * n
 
for i in a:
  res[i - 1] += 1
  
for i in res:
  print(i)
### BUGGY CODE ###

n, c = map(int, input().split())
S, T, C = [], [], []
for i in range(n):
    s, t, x = map(int, input().split())
    S.append(s)
    T.append(t)
    C.append(x)
mx_t = 200002
R = [0]*mx_t
for cc in range(1, c+1):
    TZ = [0]*mx_t
    for i in range(n):
        if C[i] == cc:
            TZ[2*S[i] - 1] += 1
            TZ[2*T[i]] -= 1
    for i in range(mx_t - 1):
        TZ[i+1] += TZ[i]
        if TZ[i+1] > 0: R[i+1] += 1
print(max(R))



### FIXED CODE ###

N, C = map(int, input().split())
STC = [[*map(int, input().split())] for _ in range(N)]
mx_t = 200002
R = [0]*mx_t
for cc in range(1, C+1):
    TZ = [0]*mx_t
    for s,t,c in STC:
        if c == cc:
            TZ[2*s - 1] += 1
            TZ[2*t] -= 1
    for i in range(mx_t - 1):
        TZ[i+1] += TZ[i]
        if TZ[i+1] > 0: R[i+1] += 1
print(max(R))
### BUGGY CODE ###

import bisect
import sys
sys.setrecursionlimit(10**9)

def main():
    N = int(input())
    X = []
    for _ in range(N):
        a,b = map(int,input().split())
        bisect.insort(X,(b,a))

    x = 0
    while len(X) > 0:
        b,a = X.pop(0)
        # print(b,a,x)
        if x + a > b:
            print("No")
            exit()

        x += a

    print("Yes")



if __name__ == "__main__":
  main()


### FIXED CODE ###

from collections import deque
import bisect
import sys
sys.setrecursionlimit(10**9)

def main():
    N = int(input())
    X = []
    for _ in range(N):
        a,b = map(int,input().split())
        X.append((b,a))

    x = 0
    X.sort(key=lambda x: x[0])
    X = deque(X)
    l = len(X)
    for _ in range(l):
        b,a = X.popleft()
        # print(b,a,x)
        if x + a > b:
            print("No")
            exit()

        x += a

    print("Yes")



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

A, B, C, K = map(int, input().split())
res = 0
total = 0
for a in range(A+1):
    for b in range(B+1):
        for c in range(C+1):
            if K == a + b + c:
                total = a*1 + b*0 + c*-1
                if res < total:
                    res = total
print(total)

### FIXED CODE ###

A, B, C, K = map(int, input().split())

xa = min(A, K)
K = K - xa
xb = min(B, K)
K = K - xb
xc = min(C, K)
total = xa*1 + xb*0 + xc*-1
print(total)
### 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()))

ab = []
for i in range(x):
  for j in range(y):
    ab.append(a[i] + b[j])
ab = sorted(ab, reverse=True)

abc = []
for i in range(min(k, len(ab))):
  for j in range(z):
    abc.append(ab[i] + c[j])
abc = sorted(abc, reverse=True)

for i in range(k):
  print(abc[i])


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

ab = []
for i in range(x):
  for j in range(y):
    ab.append(a[i] + b[j])
ab = sorted(ab, reverse=True)

abc = []
for i in range(min(k, len(ab))):
  for j in range(z):
    abc.append(ab[i] + c[j])
abc = sorted(abc, reverse=True)

for i in range(k):
  print(abc[i])
### BUGGY CODE ###

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

a = list(s)
a = [ord(i) for i in a]
b = sorted(a)
m = b[0]
n = 0
c = []
INF = 97+26
while True:
    a1 = [i for i in range(len(s)) if a[i] == m]

    for i in a1:
        j = 0
        while i+j < len(s):
            if s[i:i+j+1] not in c:
                c.append(s[i:i+j+1])
            j += 1
    if len(c) >= k:
        break
    while b[n] == m:
        n += 1
    m = b[n]
c.sort()
print(c[k-1])


### FIXED CODE ###

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

a = list(s)
a = [ord(i) for i in a]
b = sorted(set(a))
c = []
INF = 97+26
for m in b:
    a1 = [i for i in range(len(s)) if a[i] == m]

    for i in a1:
        j = 0
        for j in range(k):
            if s[i:i+j+1] not in c:
                c.append(s[i:i+j+1])
                c.sort()
            if len(c) > 5:
                del c[-1]
            j += 1
            if i + j >= len(s):
                break
    if len(c) >= k:
        break

print(c[k-1])
### BUGGY CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()

res = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        idx = bisect_left(L[j+1:], L[i]+L[j])
        res += idx

print(res)

### FIXED CODE ###

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

#二分探索
from bisect import bisect_left
#input
N = int(input())
#print(N)

A = list(map(int, input().split())) #この表記について...
B = list(map(int, input().split()))
C = list(map(int, input().split()))
#print(A,B,C)

#sort 昇順に並び替え
A.sort()
B.sort()
C.sort()

#3重を考えるとC<B<A
ans = 0
for i in range(N):
    M = bisect_left(B, C[i]) 
    #ans += M
    for j in range(M):
        ans += bisect_left(A,B[j])


print(ans)

### FIXED CODE ###

from bisect import bisect_left
from bisect import bisect_right
#input
N = int(input())
#print(N)

A = sorted(list(map(int, input().split()))) #この表記について...
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
#print(A,B,C)

#sort 昇順に並び替え
#A.sort()
#B.sort()
#C.sort()
ans = 0
for i in range(N):
    ab = bisect_left(A,B[i])
    bc = N-bisect_right(C,B[i])
    #print(ab, end='  ')
    #print(bc)
    ans += ab*bc
print(ans)
### BUGGY CODE ###

def solve():
    from sys import stdin
    f_i = stdin
    
    mod = 10 ** 9 + 7
    
    N, K = map(int, f_i.readline().split())
    A = sorted(map(int, f_i.readline().split()))
    
    comb = 1
    ans = A[K-1] - A[N-K]
    for i, j, A_s, A_t in zip(range(K, N), range(1, N), A[K:], A[N-K-1::-1]):
        comb = comb * i // j
        ans += (A_s - A_t) * comb
    
    print(ans % mod)

solve()

### FIXED CODE ###

def solve():
    from sys import stdin
    f_i = stdin
    
    mod = 10 ** 9 + 7
    
    N, K = map(int, f_i.readline().split())
    A = sorted(map(int, f_i.readline().split()))
    
    comb = 1
    ans = A[K-1] - A[N-K]
    for i, j in zip(range(K, N), range(1, N)):
        comb = comb * i * pow(j, mod - 2, mod) % mod
        ans += (A[i] - A[N-i-1]) * comb
        ans %= mod
    
    print(ans)

solve()
### BUGGY CODE ###

def compute_score(p, c, solved):
    score = 0
    for i, (p_i, c_i, s_i) in enumerate(zip(p, c, solved)):
        score += (i + 1) * 100 * s_i
        if p_i == s_i:
            score += c_i

    return score


if __name__ == '__main__':
    d, g = map(int, input().split())
    p = []
    c = []
    for _ in range(d):
        p_i, c_i = map(int, input().split())
        p.append(p_i)
        c.append(c_i)

    # d = 2
    # g = 700
    # p = [3, 5]
    # c = [500, 800]

    # d = 5
    # g = 25000
    # p = [20, 40, 50, 30, 1]
    # c = [1000, 1000, 1000, 1000, 1000]

    solved = tuple([0 for _ in range(d)])
    scores = dict()
    scores[solved] = 0

    min_n_solved = 10 * 100
    next_solved_set = {solved}
    while True:
        solved = next_solved_set.pop()

        for i in range(d):
            # complete i-th problems
            if solved[i] == p[i]:
                continue

            next_solved = list(solved)
            next_solved[i] += 1
            next_solved = tuple(next_solved)

            if next_solved in scores:
                continue

            next_score = compute_score(p, c, next_solved)
            if g <= next_score:
                min_n_solved = min(min_n_solved, sum(next_solved))
                continue

            scores[next_solved] = next_score
            next_solved_set.add(next_solved)

        if len(next_solved_set) == 0:
            break

    print(min_n_solved)


### FIXED CODE ###

if __name__ == '__main__':
    d, g = map(int, input().split())
    p = []
    c = []
    for _ in range(d):
        p_i, c_i = map(int, input().split())
        p.append(p_i)
        c.append(c_i)

    # d = 2
    # g = 700
    # p = [3, 5]
    # c = [500, 800]

    # d = 5
    # g = 25000
    # p = [20, 40, 50, 30, 1]
    # c = [1000, 1000, 1000, 1000, 1000]

    ans = 10 * 100
    for bit in range(1 << d):
        sum_score = 0
        n_solved = 0
        # 1つも全完しないケースもこのfor文に含まれる
        for i in range(d):
            if bit & (1 << i) != 0:
                sum_score += c[i] + 100 * p[i] * (i + 1)
                n_solved += p[i]

        if g <= sum_score:
            ans = min(ans, n_solved)
            continue

        for i in range(d - 1, -1, -1):
            # already solved
            if bit & (1 << i) != 0:
                continue

            for j in range(p[i]):
                if g <= sum_score:
                    break
                sum_score += 100 * (i + 1)
                n_solved += 1

        ans = min(ans, n_solved)

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

N = int(input())
A = list(map(int, input().split()))
i_list = [a + i + 1 for i, a in enumerate(A)]

ans = 0
for j in range(N):
    ans += i_list[:j+1].count(j+1-A[j])
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
#i_list = [a + i + 1 for i, a in enumerate(A)]

ans = 0
mp = {}
for i in range(N):
    i_kou = i + 1 + A[i]
    if i_kou in mp:
        mp[i_kou] += 1
    else:
        mp[i_kou] = 1
    j_kou = i + 1 - A[i]
    if j_kou in mp:
        ans += mp[j_kou]
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n,q=map(int,input().split())
t=[[] for _ in range(n)]
c=[0 for _ in range(n)]

for i in range(n-1):
  a,b=map(int,input().split())
  t[a-1].append(b-1)
  t[b-1].append(a-1)

for i in range(q):
  p,x=map(int,input().split())
  c[p-1]+=x

def dsf(ci,pi):
  for i in t[ci]:
    if i == pi:
      continue
    c[i] += c[ci]
    dsf(i, ci)

dsf(0,-1)

print(*c)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline

n,q=map(int,input().split())
t=[[] for _ in range(n)]
c=[0 for _ in range(n)]

for i in range(n-1):
  a,b=map(int,input().split())
  t[a-1].append(b-1)
  t[b-1].append(a-1)

for i in range(q):
  p,x=map(int,input().split())
  c[p-1]+=x

def dsf(ci,pi):
  for i in t[ci]:
    if i != pi:
      c[i] += c[ci]
      dsf(i, ci)

dsf(0,-1)

print(*c)
### BUGGY CODE ###

#!/usr/bin/env python3
import math

N = int(input().split()[0])
a_list = list(map(int, input().split()))

total = sum(a_list)
work_list = []

for i in range(N - 1):
    sunuke = sum(a_list[: i + 1])
    arai = total - sunuke
    work_list.append(abs(sunuke - arai))

ans = min(work_list)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import math

N = int(input().split()[0])
a_list = list(map(int, input().split()))

total = sum(a_list)
work_list = []
sunuke = 0

for i in range(N - 1):
    sunuke += a_list[i]
    arai = total - sunuke
    work_list.append(abs(sunuke - arai))

ans = min(work_list)
print(ans)
### BUGGY CODE ###

K,S=input().split()
L=0
for X in range(0,int(K)+1):
    for Y in range(0,int(K)+1):
        Z=int(S)-(X+Y)
        if 0<=Z<=int(K):
            L+=1
        
print(L)        
        

### FIXED CODE ###

K,S=input().split()
k=int(K)
s=int(S)
L=0
for X in range(0,k+1):
    for Y in range(0,k+1):
        Z=s-(X+Y)
        if 0<=Z<=k:
            L+=1
        
print(L)
### BUGGY CODE ###

from fractions import gcd

MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

L = A[0]
for i in range(1, N):
    L = L * A[i] // gcd(L, A[i])

ans = 0
for i in range(N):
    ans += L // A[i]
    ans %= MOD
print(ans)


### FIXED CODE ###

from fractions import gcd
from functools import reduce

MOD = 10 ** 9 + 7
N = int(input())
A = list(map(int, input().split()))

L = reduce(lambda x, y: x * y // gcd(x, y), A)

ans = 0
for i in range(N):
    ans += L // A[i]
print(ans % MOD)
### BUGGY CODE ###

def main():
    N = int(input())
    X = int(input(), 2)
    ans = []
    for i in range(N-1, -1, -1):
        count = 0
        target = 1 << i
        Xi = X ^ target

        # process
        while Xi:
            count += 1
            popcount = bin(Xi).count("1")
            Xi %= popcount

        ans.append(count)
    
    print(*ans, sep="\n")
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N = int(input())
    X = input()
    
    def popcount(x):
        '''xの立っているビット数をカウントする関数
        (xは64bit整数)'''

        # 2bitごとの組に分け、立っているビット数を2bitで表現する
        x = x - ((x >> 1) & 0x5555555555555555)

        # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
        x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

        x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
        x = x + (x >> 8) # 16bitごと
        x = x + (x >> 16) # 32bitごと
        x = x + (x >> 32) # 64bitごと = 全部の合計
        return x & 0x0000007f

    ans = []
   
    f = [0] * N
    # preprocess 1
    for i in range(1, N):
        pc = popcount(i)
        j =  i % pc
        f[i] = f[j] + 1
    
    # preprocess 2
    X_COUNT = X.count("1")
    X = tuple(map(int, tuple(X)))
    rem_plus = [0] * N
    rem_minus = [0] * N
    two_factor = 1
    for i in range(N):
        rem_plus[i] = two_factor
        two_factor *= 2
        two_factor %= (X_COUNT+1)

    if X_COUNT > 1:
        two_factor = 1
        for i in range(N):
            rem_minus[i] = two_factor
            two_factor *= 2
            two_factor %= (X_COUNT-1)


    X_rem_plus = 0
    X_rem_minus = 0
    two_factor = 1
    for c in X[::-1]:
        X_rem_plus += two_factor*c
        X_rem_plus %= (X_COUNT+1)
        two_factor *= 2
        two_factor %= (X_COUNT+1)
    
    if X_COUNT > 1:
        two_factor = 1
        for c in X[::-1]:
            X_rem_minus += two_factor*c
            X_rem_minus %= (X_COUNT-1)
            two_factor *= 2
            two_factor %= (X_COUNT-1)
    
    for i, c in enumerate(X):
        if c:
            if X_COUNT > 1:
                rem = X_rem_minus - rem_minus[N-1-i]
                rem %= (X_COUNT-1)
                ans.append(f[rem]+1)
            elif X_COUNT == 1:
                ans.append(0)
            else:
                ans.append(0)
        else:
            rem = X_rem_plus + rem_plus[N-1-i]
            rem %= (X_COUNT+1)
            ans.append(f[rem]+1)
   
    print(*ans, sep="\n")

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

from collections import Counter
n=int(input())
s=list(input())
C=Counter(s)
r,g,b=C["R"],C["G"],C["B"]
ans=r*g*b

for i in range(n-2):
    for j in range(i+1,n-1):
        if 2*j-i<=n-1 and s[i]!=s[j] and s[j]!=s[2*j-i] and s[2*j-i]!=s[i]:
                ans-=1

print(ans)

### FIXED CODE ###

from collections import Counter
n=int(input())
s=list(input())
C=Counter(s)
r,g,b=C["R"],C["G"],C["B"]
ans=r*g*b

for i in range(n-2):
    for j in range(i+1,n-1):
        k=2*j-i
        if k<=n-1 and s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
                ans-=1

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

n = int(input())
a = list(map(int, input().split()))

cnt = 0
for i in range(n):
    for j in range(i + a[i], n):
        if j - i == a[i] + a[j]:
            cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
r = {}
for i in range(n):
    try:
        r[i-a[i]] += 1
    except:
        r[i-a[i]] = 1
cnt = 0
for i in range(n):
    r[i-a[i]] -= 1
    try:
        cnt += r[i+a[i]]
    except:
        pass
print(cnt)
### BUGGY CODE ###

S = input()
subS = S
cnt = 0
while True:
    flg = True
    if "01" in subS:
        flg = False
        subS = subS.replace("01", "", 1)
        cnt += 2
    if "10" in subS:
        flg = False
        subS = subS.replace("10", "", 1)
        cnt += 2
    if flg:
        break
print(cnt)


### FIXED CODE ###

S = input()

zeroSum = 0
oneSum = 0
for _ in S:
  if _ == "0":
    zeroSum += 1
  if _ == "1":
    oneSum += 1

t = max(zeroSum, oneSum) - min(zeroSum, oneSum)
print(len(S) - t)
### BUGGY CODE ###

n = int(input())

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

nums = [0] * (10**5+1)
nums[0] = a.count(0) + a.count(1)
nums[(10**5)] = a.count((10**5)-1) + a.count((10**5))
for i in range(1, (10**5)):
  nums[i] = a.count(i-1) + a.count(i) + a.count(i+1)
  
print(max(nums))

### FIXED CODE ###

n = int(input())

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

d = {}

for i in a:
  for j in range(i - 1, i + 2): #aの値の両隣まで
    d[j] = d.get(j, 0) + 1#getは第一引数で指定したキーがなかったら第二引数で指定した値を戻す
    
    
print(max(d.values()))
### BUGGY CODE ###

def main():
  n,m=map(int,input().split())
  x=list(map(int,input().split()))
  xmod=[y%m for y in x]
  from collections import Counter
  cxmod=dict(Counter(xmod))
  cx=dict(Counter(x))
  keys=list(cxmod.keys())
  ans1,ans2=0,0 # ams1:m倍になるペア、ans2:同数のペア。ans1からもとめる
  d2={}
  for k in keys:
    if k==0:
      ans1+=cxmod[k]//2
      cxmod[k]-=2*(cxmod[k]//2)
    else:
      if k==m-k:
        ans1+=cxmod[k]//2
        cxmod[k]-=2*(cxmod[k]//2)
      elif m-k in keys:
        tmp=min(cxmod[k],cxmod[m-k])
        ans1+=tmp
        cxmod[k]-=tmp
        cxmod[m-k]-=tmp
  for k,v in cx.items():
    if v>=2 and cxmod[k%m]>=2:
      tmp=min(v//2,cxmod[k%m]//2)
      ans2+=tmp
      cxmod[k%m]-=tmp*2

  print(ans1+ans2)
if __name__=='__main__':
  main()



### FIXED CODE ###

def main():
  n,m=map(int,input().split())
  x=list(map(int,input().split()))
  #xmod=[y%m for y in x]
  from collections import Counter
  cx=Counter(x)
  cxmod={}
  for k in cx:
    if k%m in cxmod:
      cxmod[k%m]+=cx[k]
    else:
      cxmod[k%m]=cx[k]
  keys=cxmod.keys()
  ans1,ans2=0,0 # ams1:m倍になるペア、ans2:同数のペア。ans1からもとめる
  for k in keys:
    if k==0:
      ans1+=cxmod[k]//2
      cxmod[k]-=2*(cxmod[k]//2)
    else:
      if k==m-k:
        ans1+=cxmod[k]//2
        cxmod[k]-=2*(cxmod[k]//2)
      elif m-k in keys:
        tmp=min(cxmod[k],cxmod[m-k])
        ans1+=tmp
        cxmod[k]-=tmp
        cxmod[m-k]-=tmp
  for k in cx:
    v=cx[k]
    if v>=2 and cxmod[k%m]>=2:
      tmp=min(v//2,cxmod[k%m]//2)
      ans2+=tmp
      cxmod[k%m]-=tmp*2

  print(ans1+ans2)
if __name__=='__main__':
  main()
### BUGGY CODE ###

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

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


### FIXED CODE ###

from collections import deque
S = deque(str(input()))
Q = int(input())
count = 0
for i in range(Q):
    tmp = list(input().split())
    if tmp[0]=="1":
        count += 1
    else:
        if tmp[1]=="1" and count%2==0 or tmp[1]=="2" and count%2==1:
            S.appendleft(tmp[2])
        elif tmp[1]=="2" and count%2==0 or tmp[1]=="1" and count%2==1:
            S.append(tmp[2])
if count%2==0:
    ans = "".join(S)
    print(ans)
else: 
    S.reverse()
    ans = "".join(S)
    print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000000)
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split()))for _ in range(q)]
def dfs(li):
  ans=0
  for a,b,c,d in abcd:
    if li[b-1]-li[a-1]==c:ans+=d
  for i in range(n-1):
    if li[i]<li[i+1]:
      li[i]+=1
      ans=max(ans,dfs(li))
      li[i]-=1
  if li[-1]!=m:
    li[-1]+=1
    ans=max(ans,dfs(li))
    li[-1]-=1
  return ans
print(dfs([1]*n))


### FIXED CODE ###

import itertools
n,m,q=map(int,input().split())
abcd=[list(map(int,input().split()))for _ in range(q)]
ans=0
for i in itertools.combinations_with_replacement(range(m),n):
  anss=0
  for a,b,c,d in abcd:
    if i[b-1]-i[a-1]==c:anss+=d
  ans=max(ans,anss)
print(ans)
### BUGGY CODE ###

def counter(lss):
    n = len(lss)
    cnt = 0
    anums = []
    for i in range(1,(n + 1)):
        anum = 0
        for j in range(n):
            if (i == lss[j]):
                anum += 1
        cnt += (anum * (anum - 1)) // 2
    return cnt

n = int(input())

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

for k in range(n):
    if (k == 0):
        lss = ls[1:n]
    elif (k == n-1):
        lss = ls[0:n-1]
    else:
        lss = ls[0:k] + ls[k + 1:n]
    print(counter(lss))





### FIXED CODE ###

from collections import Counter
def cmb(n):
    if n < 2:
        return 0
    else:
        return (n * (n-1)) // 2

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

cs = Counter(ls)
s = 0

for v in cs.values():
    s += cmb(v)

for a in ls:
    print(s - cmb(cs[a]) + cmb(cs[a] - 1))
### BUGGY CODE ###

#coding:utf-8
#1_1_D
n = int(input())
maxv = -2 * 10 ** 9
prices = [int(input()) for x in range(n)]

for i in range(1, n):
    for j in range(i):
        if prices[i] - prices[j] > maxv:
            maxv = prices[i] - prices[j]

print(maxv)

### FIXED CODE ###

#coding:utf-8
#1_1_D
n = int(input())
prices = [int(input()) for x in range(n)]
maxv = -2 * 10 ** 9
minv = prices[0]
for i in range(1, n):
    maxv = max(maxv, prices[i] - minv)
    minv = min(minv, prices[i])

print(maxv)