Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python3

def main():
    from itertools import chain
    S = input()
    Q = int(input())
    Queries = [input().split() for _ in range(Q)]
    H_T = H, T = [], []
    flag = 0
    for query in Queries:
        if len(query) == 1:
            flag ^= 1
            continue
        _, f, c = query
        H_T[(int(f) + flag) % 2].append(c)
    if flag:
        print(''.join(chain(reversed(H), S, T)))
    else:
        print(''.join(chain(reversed(T), S, H)))

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def main():
    from itertools import chain
    S = input()
    Q = int(input())
    Queries = [input().split() for _ in range(Q)]
    H_T = H, T = [], []
    flag = 0
    for query in Queries:
        if len(query) == 1:
            flag ^= 1
            continue
        _, f, c = query
        H_T[(int(f) + flag - 1) % 2].append(c)
    t = ''.join(chain(reversed(H), S, T))
    if flag:
        t = reversed(t)
    print(''.join(t))


if __name__ == '__main__':
    main()
# coding: utf-8
# Your code here!

from datetime import datetime
K = int(input())
start = datetime.now()
def KSum(n):
    k = 0
    for i in str(n):
        k += int(i)
    return k

m = KSum(K)
j = 1
while((datetime.now()-start).total_seconds() < 1.8):
    for x in range(100):
	    P = KSum(K*j)
    	if m > P:
        	m = P
    	j += 1
print(m)


### FIXED CODE ###

S=input()
T=input()
if S==T[::-1]:
  print("YES")
else:
  print("NO")
import sys
input = sys.stdin.readline
n = int(input())

g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append((v, w))
    g[v].append((u, w))

chk = [0]*n
chk[0] = 1

def dfs(now, prev):
    global chk
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next[0] != prev:
          if next[1]%2 == 0:
            chk[next[0]] = chk[now]
          elif next[1]%2 == 1:
            chk[next[0]] = (chk[now]*-1)
          
          dfs(next[0], now)
        
dfs(0,-1)
#print(chk)
chk = tuple(chk)
for i in chk:
  if i == 1:
    print(1)
  else:
    print(0)

### FIXED CODE ###

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

g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append((v, w))
    g[v].append((u, w))

chk = [0]*n
chk[0] = 1

def dfs(now, prev):
    global chk
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next[0] != prev:
          if next[1]%2 == 0:
            chk[next[0]] = chk[now]
          elif next[1]%2 == 1:
            chk[next[0]] = (chk[now]*-1)
          
          dfs(next[0], now)
        
dfs(0,-1)
chk = tuple(chk)
for i in chk:
  if i == 1:
    print(1)
  else:
    print(0)
import math
N, a, b = map(int, input().strip().split())

if (b-a)%2==0:
    ans=int(math.round((b-a)/2))
else:
    ans=min(a-1,N-b)+math.ceil((b-a)/2)
print(ans)

### FIXED CODE ###

import math
N, a, b = map(int, input().strip().split())

if (b-a)%2==0:
    ans=(b-a)//2
else:
    ans=min(a-1,N-b)+1+(b-a)//2
print(ans)
n = int(input())
table = []
for i in range(n):
    table.append(input())
    
print("{} {} {}".format(max(table),min(table),sum(table)))


### FIXED CODE ###

n = input()
table = list(map(int,input().split()))
print("{} {} {}".format(min(table),max(table),sum(table)))
,K,D = map(int,input().split())

y = abs(X)//D

if K<=y:
    print(abs(abs(X)-K*D))

else  :
    a = (X-y*D)
    b = (X-(y+1)*D)
    
    C = abs(a)
    D = abs(b)
    
    if (K-y)%2==0:
        print(C)
    else:
        print(D)


#print(y+1)
#print(1000000000000000)

### FIXED CODE ###

X,K,D = map(int,input().split())

y = abs(X)//D

if K<=y:
    print(abs(abs(X)-K*D))

else  :
    a = (abs(X)-y*D)
    b = (abs(X)-(y+1)*D)
    
    C = abs(a)
    D = abs(b)
    
    if (K-y)%2==0:
        print(C)
    else:
        print(D)


#print(y+1)
#print(1000000000000000)
n = int(input())
a=int(n/4)+1
b=int(n/7)+1
ans=0
for i in range(a+1):
  for j in range(b+1):
    if 4*i+7*j=n:
      ans+=1
if ans==0:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

n = int(input())
a=int(n/4)+1
b=int(n/7)+1
ans=0
for i in range(a+1):
  for j in range(b+1):
    if 4*i+7*j==n:
      ans+=1
if ans==0:
  print("No")
else:
  print("Yes")
def main():
    import sys
    N,K=list(map(int,sys.stdin.readline().split()))
    A=list(map(int,sys.stdin.readline().split()))

    Ap=[x for x in A if x>=0 ]
    Am=[abs(x) for x in A if x<0]

    if K==N:
        out=1
        for a in A:
            out*=a
            out%=10**9+7
        print(out)
        return


    if K%2==1 and len(Ap)==0:
        Am.sort()
        out=1
        for i in range(K):
            out*=Am[i]
            out%=10**9+7
        print((-out)%(10**9+7))
        return

    Ap.sort(reverse=True)
    Am.sort(reverse=True)
    
    ap_idx=0
    am_idx=0
    result=1
    for _ in range(0,K,2):
        kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk
        if K%2==0 and ap_idx+1<len(Ap):
            pmax=Ap[ap_idx]*Ap[ap_idx+1]
        elif K%2==1 and ap_idx+2<len(Ap):
            pmax=Ap[ap_idx]*Ap[ap_idx+1]
        else:
            pmax=-1

        if am_idx+1<len(Am):
            mmax=Am[am_idx]*Am[am_idx+1]
        else:
            mmax=-1

        if pmax==-1 and mmax==-1:
            break

        if pmax>mmax:
            result*=pmax
            ap_idx+=2
        else:
            result*=mmax
            am_idx+=2

        result%=(10**9+7)
    
    if K%2==1:
        result*=Ap[ap_idx]

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

main()

### FIXED CODE ###

def main():
    import sys
    N,K=list(map(int,sys.stdin.readline().split()))
    A=list(map(int,sys.stdin.readline().split()))

    Ap=[x for x in A if x>=0 ]
    Am=[abs(x) for x in A if x<0]

    if K==N:
        out=1
        for a in A:
            out*=a
            out%=10**9+7
        print(out)
        return


    if K%2==1 and len(Ap)==0:
        Am.sort()
        out=1
        for i in range(K):
            out*=Am[i]
            out%=10**9+7
        print((-out)%(10**9+7))
        return

    Ap.sort(reverse=True)
    Am.sort(reverse=True)
    
    ap_idx=0
    am_idx=0
    result=1

    for _ in range(0,K-1,2):
        if K%2==0 and ap_idx+1<len(Ap):
            pmax=Ap[ap_idx]*Ap[ap_idx+1]
        elif K%2==1 and ap_idx+2<len(Ap):
            pmax=Ap[ap_idx]*Ap[ap_idx+1]
        else:
            pmax=-1

        if am_idx+1<len(Am):
            mmax=Am[am_idx]*Am[am_idx+1]
        else:
            mmax=-1

        if pmax==-1 and mmax==-1:
            break

        if pmax>mmax:
            result*=pmax
            ap_idx+=2
        else:
            result*=mmax
            am_idx+=2

        result%=(10**9+7)
    
    if K%2==1:
        result*=Ap[ap_idx]

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

main()
n = int(input())
s = input()

if n % 2 != 0 or s[:n/2] != s[n/2:]:
  print("No")
else:
  print("Yes")
 

### FIXED CODE ###

n = int(input())
s = input()
     
if s[:n//2] == s[n//2:]:
	print("Yes")
else:
	print("No")
import numpy as np
'''
K = 2
H, W = 5, 5
a = np.array([
	[0, 0, 0, 0, 1],
	[0, 0, 0, 1, 1],
	[0, 0, 1, 1, 1],
	[0, 1, 1, 1, 1],
	[1, 1, 1, 1, 1]
])
'''

H, W, K = map(int, input().split())
a = np.array([map(int, input().split()) for _ in range(H)])

count = 0
for i in range(2 ** H - 1):
	b = np.delete(a.copy(), [j for j in range(H) if ((i >> j) & 1)], 0)
	for i in range(2 ** W - 1):
		c = np.delete(b.copy(), [j for j in range(H) if ((i >> j) & 1)], 1)
		#print(np.sum(c))
		if K==np.sum(c):
			count += 1
print(count)
print()

### FIXED CODE ###

import numpy as np
'''
K = 2
H, W = 5, 5
a = np.array([
	[0, 0, 0, 0, 1],
	[0, 0, 0, 1, 1],
	[0, 0, 1, 1, 1],
	[0, 1, 1, 1, 1],
	[1, 1, 1, 1, 1]
])
'''

def conv(c):
	#print(c)
	return int(c=='#')
H, W, K = map(int, input().split())
a = np.array([list(map(conv, input())) for _ in range(H)])
count = 0
for i in range(2 ** H - 1):
	b = np.delete(a.copy(), [j for j in range(H) if ((i >> j) & 1)], 0)
	blen = b.shape[1]
	for i in range(2 ** W - 1):
		c = np.delete(b, [j for j in range(blen) if ((i >> j) & 1)], 1)
		#print(np.sum(c))
		if K==np.sum(c):
			count += 1
print(count)
print()
s=input()
n=int(input())
strlist=[input() for i in range(n)]
for i in range(n):
  if i==1:
    s=s[::-1]
  elif i==2 and strlist[i][2] == 1:
    s = '{}{}'.format(strlist[i][4],s)
  elif i==2 and strlist[i][2] == 2:
    s = '{}{}'.format(s,strlist[i][4])
print(s)

### FIXED CODE ###

from collections import deque
s=deque(input())
n=int(input())
r=0
for i in range(n):
    strlist=input()
    if strlist[0]=='1':
        r+=1
    elif strlist[0]=='2' and strlist[2] == '1':
        if r%2==0:
            s.appendleft(strlist[4])
        else:
            s.append(strlist[4])
    elif strlist[0]=='2' and strlist[2] =='2':
        if r%2==0:
            s.append(strlist[4])
        else:
            s.appendleft(strlist[4])
if r%2==0:
    for s_ in s:
        print(s_, end='')
else:
    s.reverse()
    for s_ in s:
        print(s_, end='')
n, m = map(int, input().split())
a = list(map(int, input().split()))
cnt = 0

for i in a:
  if i >= (1/4m):
    cnt += 1

if cnt < M:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
cnt = 0
 
for i in a:
  if i >= sum(a)*(1/(4*m)):
    cnt += 1

if cnt >= m:
  print("Yes")
else:
  print("No")
a=input()
b=input()
c=input()
def g(x):
  if x=='a':
    if len(a)==0:
      y='A'
    else:
      y=a[0]
      a[0]=''
  elif x=='b':
    if len(b)==0:
      y='B'
    else:
      y=b[0]
      b[0]=''
  else:
    if len(c)==0:
      y='C'
    else:
      y=c[0]
      c[0]=''
  return y
t=g(a[0])
while t!='A' and t!='B' and t!='C':
  t=g(t)
print(t)
  

### FIXED CODE ###

a=input()
b=input()
c=input()
def s(x):
  if len(x)==1:
    return ''
  else:
    return x[1:]
def g(x):
  global a
  global b
  global c
  if x=='a':
    if len(a)==0:
      y='A'
    else:
      y=a[0]
      a=s(a)
  elif x=='b':
    if len(b)==0:
      y='B'
    else:
      y=b[0]
      b=s(b)
  else:
    if len(c)==0:
      y='C'
    else:
      y=c[0]
      c=s(c)
  return y
t=g(a[0])
while t!='A' and t!='B' and t!='C':
  t=g(t)
print(t)
import sys
   
def isort(a, n, g):
    global cnt
    for i in range(g, n):
        v = a[i]
        j = i - g
        while j >= 0 and a[j] > v:
            a[j + g] = a[j]
            j -= g
            cnt += 1
        a[j + g] = v
   
# input data
n = int(sys.stdin.readline())
a = []
for i in range(n):
    a.append(int(sys.stdin.readline()))
   
# determine m, g
g = [1]
m = 1
while True:
    x = 3 * g[m - 1] + 1
    if x >= n: break
    g.append(x)
    m += 1
g = g[::-1]
   
# 1 output m
print(m)
# 2 output g
print(' '.join(map(str, g)))
   
# sort it
cnt = 0
for i in range(m):
    isort(a, n, g[i])
   
# 3 output cnt
print(cnt)
# 4 output sorted a
print('\n'.join(map(str, a)))

### FIXED CODE ###

def insertion_sort(array, g, result):
    for i in range(g, len(array)):
        v = array[i]
        j = i - g
        while j >= 0 and array[j] > v:
            array[j + g] = array[j]
            j -= g
            result['count'] += 1
        A[j + g] = v


def g_gene(n):
    yield 1
    for i in range(2, n):
        x = int((3 ** i - 1) / 2)
        if x < n:
            yield x
        else:
            raise StopIteration()


def shell_sort(array, result):
    result['count'] = 0
    G = list(reversed(list(g_gene(len(array)))))
    m = len(G)
    result['G'] = G
    result['m'] = m
    for i in range(m):
        insertion_sort(array, G[i], result)


if __name__ == '__main__':
    import sys
    n = int(sys.stdin.readline())
    A = []
    for _ in range(n):
        A.append(int(sys.stdin.readline()))
    result = {}
    shell_sort(A, result)
    print(result['m'])
    print(' '.join(map(str, result['G'])))
    print(result['count'])
    for a in A:
        print(a)
n,m=map(int,input().split())
x=list(map(int,input().split()))
if n==1:
    print(max(x)-min(x))
elif m==1 or n>=m:
    print(0)
else:
    goukei=0
    l=[0]
    i=0
    x.sort()
    a=0
    b=0
    while i<m-1:
        a=x[i]
        b=x[i+1]
        goukei+=b-a
        l.append(b-a)
        i+=1
    for v in range(n-1):
        goukei-=max(l)
        l.remove(max(l))
    print(goukei)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
m=l[-1]
s=0
for i in range(n-1):
    s+=l[i]
print("Yes" if m<s else "No")
n = int(input())
k = int(input())
s = [str(i) for i in range(n)]

sl = s[k]
sk = sl.lower()
print(sk)


### FIXED CODE ###

N, K = (int(i) for i in input().split())
S = list(input())

S[K - 1] = S[K - 1].lower()
print(''.join(S))
from math import ceil
N, K = map(int, raw_input().split())
A = map(int, raw_input().split())

print (int(ceil((N-1)/(K-1))))


### FIXED CODE ###

import math
N, K = map(int, input().split())
input()
     
print(math.ceil((N-1)/(K-1)))
n=int(input())
a=[int(input()) for _ in range(n-1)]

for i in range(n):
    print(a.count(i+1))



### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[0]*n

for i in a:
    b[i-1]+=1

[print(i) for i in b]
def lcs(x, y, pre_lcs, pre_lcs_len):
    rec = []
    idx = []
    for c in y:
        s = 0
        for i, k in enumerate(idx):
            t = x.find(c, s) + 1
            if t < 1:
                break
            if t < k:
                idx[i] = t
            s = k
        else:
            t = x.find(c, s) + 1
            if t:
                idx.append(t)
        rec.append(idx.copy())
    
    lcs_len = len(idx)
    if lcs_len > pre_lcs_len:
        lcs = ''
        pos = len(idx) - 1
        for line, yc in zip(rec[::-1], y[::-1]):
            i = line[pos] - 1
            xc = x[i]
            if xc == yc:
                lcs += xc
                if pos == 0:
                    return (lcs[::-1], lcs_len)
                pos -= 1
    else:
        return (pre_lcs, pre_lcs_len)

def solve():
    import sys
    file_input = sys.stdin
    ans_out = []
    for s in file_input:
        s = s.rstrip()
        if s == '#END':
            break
        s_len = len(s)
        sep = s_len // 2
        ans, ans_len = lcs(s[:sep], s[sep:], '', 0)
        while sep > ans_len:
            ans, ans_len = lcs(s[:-sep], s[-sep:], ans, ans_len)
            sep -= 1
            ans, ans_len = lcs(s[:sep], s[sep:], ans, ans_len)
        ans_out.append(ans)
    print(*ans_out, sep='\n')

solve()


### FIXED CODE ###

def lcs(x, y, pre_lcs, pre_lcs_len):
    pm = dict((zip('ABCDEFGHIJKLMNOPQRSTUVWXYZ', [0] * 26)))
    for c in pm:
        for i, xc in enumerate(x):
            if c == xc:
                pm[c] |= (1 << i)
    
    V = (1 << len(x)) - 1
    rec = []
    
    for yc in y:
        V = ((V + (V & pm[yc])) | (V & ~pm[yc]))
        rec.append(bin(V)[-len(x):])
    
    lcs_len = bin(V)[-len(x):].count('0')
    
    if lcs_len > pre_lcs_len:
        rx = x[::-1]
        lcs = ''
        idx = 0
        for v, yc in zip(rec[::-1], reversed(y)):
            idx = v.find('0', idx)
            if yc == rx[idx]:
                lcs += yc
                if len(lcs) == lcs_len:
                    return (lcs[::-1], lcs_len)
                idx += 1
    else:
        return (pre_lcs, pre_lcs_len)

from sys import stdin

def solve():
    file_input = stdin
    ans_out = []
    for s in file_input:
        s = s.rstrip()
        if s[0] == '#':
            break
        s_len = len(s)
        sep = s_len // 2
        ans, ans_len = lcs(s[:sep], s[sep:], '', 0)
        while sep > ans_len:
            ans, ans_len = lcs(s[:-sep], s[-sep:], ans, ans_len)
            sep -= 1
            ans, ans_len = lcs(s[:sep], s[sep:], ans, ans_len)
        ans_out.append(ans)
    print(*ans_out, sep='\n')

solve()
s=input()
s=s.replace("dream","D")
s=s.replace("erase","E")
n=len(s)
i=0
while i<n:
    if s[i]=="D":
        if i+2<n:
            if s[i:i+3]=="Der":
                i+=3
            else:
                i+=1
        else:
            i+=1
    elif s[i]=="E":
        if i+1<n:
            if s[i:i+2]=="Er":
                i+=2
            else:
                i+=1
        else:
            i+=1
    else:
        break
else:
    print("YES")
    sys.exit()
print("NO")

### FIXED CODE ###

s=input()
s=s.replace("dream","D")
s=s.replace("erase","E")
s=s.replace("Der","M")
s=s.replace("Er","M")
s=s.replace("D","M")
s=s.replace("E","M")
s=s.replace("M","")
if s:
    print("NO")
else:
    print("YES")
import time

sec = int(intput())

print((sec - day * 86400).strftime("H:M:S"))

### FIXED CODE ###

sec = int(input())
h = int(sec / 3600)
m = int((sec - 3600 * h) / 60)
s = sec - 3600 * h - 60 * m
print(str(h) + ":" + str(m) + ":" + str(s))
def main():

    N,M = map(int,input().split())
    A = [i for i in map(int,input().split())]
    A.sort()
    tmpC = 0
    targetList = []

    for i in range(M):

        element = list(map(int,input().split()))
        targetList.append(element)

    targetList.sort(key=lambda x:x[1],reverse=True)
    
    flag = False
    ans = 0
    for b,c in targetList:
        for j in range(b):
            if A[tmpC] < c and N > tmpC:
                ans += c
                tmpC +=1
            else:
                flag = True
                break
        if flag:
            break
    
    if tmpC < N:

        ans += sum(A[tmpC:])


    print(ans)






if __name__== "__main__":
    main() 


### FIXED CODE ###


def main():

    N,M = map(int,input().split())
    A = [i for i in map(int,input().split())]
    A.sort()
    tmpC = 0
    targetList = []

    for i in range(M):

        element = list(map(int,input().split()))
        targetList.append(element)

    targetList.sort(key=lambda x:x[1],reverse=True)
    
    flag = False
    ans = 0
    for b,c in targetList:
        for j in range(b):
            if N > tmpC and A[tmpC] < c:
                ans += c
                tmpC +=1
            else:
                flag = True
                break
        if flag:
            break
    
    if tmpC < N:

        ans += sum(A[tmpC:])


    print(ans)






if __name__== "__main__":
    main()
a,op,b=map(str,input().split())
a=int(a)
b=int(b)

print("%d %d %0.5f",a/b,a%b,a/b)


### FIXED CODE ###

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

print("%d %d %0.5f"%(a/b,a%b,a/b))
v = []
v = str(inp).splitlines()
dif_max = -200000

for i in range(len(v)):
    v[i] = int(v[i])

len = v[0]
for i in range(2, len + 1, 1):
    for j in range(i + 1, len + 1, 1):
        dif = v[j] - v[i]
        dif_max = dif if dif_max < dif else dif_max

print("{}".format(dif_max))

### FIXED CODE ###

cnt = int(input())
dif_max = -1000000000
v_min = 1000000000

for i in range(cnt):
    buf = int(input())
    if i > 0:
        dif_max = dif_max if buf - v_min < dif_max else buf - v_min
    v_min = buf if buf < v_min else v_min
print(dif_max)
n = int(input())
h = list(map(int,input().split()))
c =0

for i in range(n-1):
    if (h[i+1]-h[i] == 1) and (h[i+2] >= h[i]):
        c += 1
    else:
        pass
if c == 1:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
c = 0

for i in range(n-1):
    if h[i] <= h[i+1]-1:
        h[i+1] = h[i+1]-1
    elif h[i] == h[i+1]:
        continue
    else:
        c = 1
if c == 1:
    print('No')
else:
    print('Yes')
bilding = [[[0 for i in range(10)] for j in range(3)]for k in range(4)]

n = int(input())
i = 0
while i < n:
    b, f, r, v = map(int, raw_input().split())
    bilding[r][f][b] += v
    i += 1

i = 0
j = 0
k = 0
while i < 4:
    while j < 3:
        floar = ""
        while k < 10:
            floar += str(bilding[k][j][i])
            k += 1
        print floar
        j += 1
    if i < 3:
        print "####################"
    i += 1

### FIXED CODE ###

bilding = [[[0 for x in range(10)] for x in range(3)]for x in range(4)] 
n = int(input())
for k in range(n):
    b, f, r, v = map(int, raw_input().split())
    bilding[b-1][f-1][r-1] += v

for b in range(4):
    for f in range(3):
        print(" "+" ".join(map(str, bilding[b][f])))
    if b != 3:
        print("#"*20)
N = int(input())
h = input().rstrip().split(' ')
h.insert(0,-1)
h = list(map(int,h))

l = [-1]*(N-1)
l.insert(0,0)
l.insert(0,0)

def cost_min(n):
    #n番目までで最小のコストを考える
    if(l[n] != -1):
        return l[n]
    else:
        l[n] = min([cost_min(n-1) + abs(h[n]-h[n-1]),cost_min(n-2) + abs(h[n]-h[n-2])])
        return l[n]

print(cost_min(N))

### FIXED CODE ###

N = int(input())
h = input().rstrip().split(' ')
h.insert(0,0)
h = list(map(int,h))

#ここで保存しておく
l = [-1]*(N-1)
l.insert(0,0)
l.insert(0,0)

def cost_min(n):
    #n番目までで最小のコストを考える
    if(l[n] != -1):
        return l[n]
    else:
        l[n] = min([cost_min(n-1) + abs(h[n]-h[n-1]),cost_min(n-2) + abs(h[n]-h[n-2])])
        return l[n]

def cost_min_bottomup(n):
    if(n<2):
        return 0
    t_0 = 0
    t_1 = abs(h[2] - h[1])
    ans_0 = 0
    ans_1 = t_1
    for i in range(n-2):
        t_0 = ans_0 + abs(h[i+3]-h[i+1])
        t_1 = ans_1 + abs(h[i+3]-h[i+2])
        ans_0 = ans_1
        ans_1 = min([t_0,t_1])
    return ans_1

#print(cost_min(N))
print(cost_min_bottomup(N))
import math
from functools import reduce

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


N = int(input())

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

print(gcd(A))

### FIXED CODE ###

N = int(input())

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

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
        
a = A[0]
for i in range(N):
    a = gcd(a,A[i])

print(a)
del = list(map(int, input().split()))
n = len(del)
sum = 0
i = 0


print(sum)



### FIXED CODE ###

n = int(input())
deliciousness = list(map(int, input().split()))
sum = 0
i = 0

while i < n - 1:
  k = i
  while k < n - 1:
    k += 1
    sum += deliciousness[i] * deliciousness[k]
  i += 1
  
print(sum)
a, b = map(int, input().split())
if a*b/2 % 0:
  print("Even")
  else:
    print("Odd")
    

### FIXED CODE ###

a, b = map(int, input().split())
if a * b % 2 == 0:
  print("Even")
else:
    print("Odd")
L,R = map(int,(input().split()))
List = []

for i in range(L,R+1):
    for j in range(i+1,R):
        List.append(i*j%2019)
print(min(List))

### FIXED CODE ###

L,R = map(int,(input().split()))
mod = 2019
Min = 2018
for i in range(L,min(L+mod,R)):
    for j in range(i+1,min(L+mod,R+1)):
        Min = min(i*j%2019,Min)
print(Min)
N = int(input())
D.sort(reverse = True)
A = []
B = []
for i in range(N):
    if i%2==0:
        A.append(D[i])
    else:
        B.append(D[i])

print(sum(A)-sum(B))


### FIXED CODE ###

N = int(input())
D = list(map(int,input().split()))
D.sort(reverse = True)
A = []
B = []
for i in range(N):
    if i%2==0:
        A.append(D[i])
    else:
        B.append(D[i])
 
print(sum(A)-sum(B))
H,W = map(int,input().split())
a = map(int,input().split())

c = [0]*len(a)
n = 0
sign = 1
for h in range(H):
    state = [0]*W
    for w in range(W):
        if c[n]>=a[n]:
            n += 1
        state[w] = str(n+1)
        c[n] += 1
    sign = (sign+1)%2
    if sign:
        state = state[::-1]
    print(' '.join(state))

### FIXED CODE ###

H,W = map(int,input().split())
N = int(input())
a = list(map(int,input().split()))

c = [0]*N
n = 0
sign = 1
for h in range(H):
    state = [0]*W
    for w in range(W):
        if c[n]>=a[n]:
            n += 1
        state[w] = str(n+1)
        c[n] += 1
    sign = (sign+1)%2
    if sign:
        state = state[::-1]
    print(' '.join(state))
s = input()
N = len(s)
print(s[0] + len(N - 2) + s[N - 1])

### FIXED CODE ###

s = input()
N = len(s)
print(s[0] + str(N - 2) + s[N - 1])
s = input()

abc = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

if s == ''.join(abc)[::-1]:
    print(-1)
    exit()
if len(s) != 26:
    for a in abc:
        if a not in abc:
            print(s+a)
            exit()
i = 25
while s[i-1] > s[i]:
    i -= 1
    #print(s[i-1], s[i])
#print(s[i-1], s[i])
tt = s[i-1]
ss = list(s[i-1:])
ss.sort()
print(s[:i-1]+ss[ss.index(tt)+1])


### FIXED CODE ###

#11208467
t="abcdefghijklmnopqrstuvwxyz"
s=input()
if s==t[::-1]:print(-1);exit()
if len(s)!=26:
  for i in t:
    if i not in s:print(s+i);exit()
i=25
while s[i-1]>s[i]:i-=1
tt=s[i-1]
ss=list(s[i-1:])
ss.sort()
print(s[:i-1]+ss[ss.index(tt)+1])