Harryxun/stf_run huggingface dataset:
import numpy as np


def div(n, d):
    if d == 2:
        return format(n, "b")[::-1].find("1")
    cnt = 0
    while n % d == 0:
        n //= d
        cnt += 1
    return cnt


n = int(input())

arr2 = []
arr5 = []
for _ in range(n):
    x = round(float(input()) * 10**9)
    arr2.append(div(x, 2))
    arr5.append(div(x, 5))

shape = arr2.shape[0]

arr2 = (np.array(arr2) + np.zeros([shape, shape], np.int64)).astype(np.int32)
arr5 = (np.array(arr5) + np.zeros([shape, shape], np.int64)).astype(np.int32)

arr2 = np.tril(arr2 + arr2.T)
arr2 -= arr2.T
arr5 = np.tril(arr5 + arr5.T)
arr5 -= arr5.T

result = (arr2 >= 18).astype(np.int32) + (arr5 >= 18).astype(np.int32)

print(np.sum(result >= 2))

### FIXED CODE ###

def div(n, d):
    cnt = 0
    while n % d == 0 and cnt < 18:
        n //= d
        cnt += 1
    return cnt


n = int(input())
dp = [[0]*19 for _ in range(19)]

ans = 0
for _ in range(n):
    x = round(float(input()) * pow(10, 9))
    two = div(x, 2)
    five = div(x, 5)
    ans += dp[18 - two][18 - five]
    for i in range(two + 1):
        for j in range(five + 1):
            dp[i][j] += 1

print(ans)
s=[input() for _ in range(int(input()))]
t=[input() for _ in range(int(input()))]
l=list(set(n))
#s内の重複消去　リストに変更
print(max(0,max(n.count(l[i])-m.count(l[i]) for i in range(len(l)))))

### FIXED CODE ###

N=int(input())
s=[input() for _ in range(N)]
M=int(input())
t=[input() for _ in range(M)]
def ans1(x):
    return s.count(x)-t.count(x)
ans2=0
ans_1=0
for S in s:
    if ans1(S)>0 and ans1(S)>ans2:
            ans2=ans1(S)
if ans2>=0:
    print(ans2)
else:
    print("0")
N = input().split()

a = N[0]
b = N[1]
c = N[2]

count = 0
for i in range(a, b):
    if c % i == 0:
       count += 1
print(count)

### FIXED CODE ###

N = input().split()

a = int(N[0])
b = int(N[1])
c = int(N[2])

count = 0
while a <= b:
    if c % a == 0:
       count += 1
    a += 1
print(count)
H,W = (int(i) for i in input().split())

goal = []
for i in range(H):
    goal.append(input())

canComplete = True

for row in range(W):
    for column in range(H):
        above = row - 1
        bottom = row + 1
        left = column - 1
        right = column + 1
        
        if goal[row][column] == "#":
            if above >= 0 and goal[above][column] == "#":
                continue
            elif bottom < H and goal[bottom][column] == "#":
                continue
            elif left >= 0 and goal[row][left] == "#":
                continue
            elif right < W and goal[row][right] == "#":
                continue
            else:
                canComplete = False
                break

if canComplete:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

H,W = (int(i) for i in input().split())

goal = []
for i in range(H):
    goal.append(input())

canComplete = True

for row in range(H):
    for column in range(W):
        above = row - 1
        bottom = row + 1
        left = column - 1
        right = column + 1
        
        if goal[row][column] == "#":
            if above >= 0 and goal[above][column] == "#":
                continue
            elif bottom < H and goal[bottom][column] == "#":
                continue
            elif left >= 0 and goal[row][left] == "#":
                continue
            elif right < W and goal[row][right] == "#":
                continue
            else:
                canComplete = False
                break

if canComplete:
    print("Yes")
else:
    print("No")
from  itertools import combinations
n,C=map(int,input().split())
d=[list(map(int,input().split())) for _ in range(C)]
c=[list(map(int,input().split())) for _ in range(n)]
a=[[0]*C for _ in range(3)]
for i in range(n):
	for j in range(n):
		a[(i+j)%3][c[i][j]-1]+=1
ans=10**9
for v in combinations(C,3):
	tmp=0
	for i in range(3):
		for j in range(30):
			tmp+=a[i][j]*c[j][v[i]]
	ans=min(ans,tmp)
print(ans)

### FIXED CODE ###

from itertools import permutations
n,C=map(int,input().split())
d=[list(map(int,input().split())) for _ in range(C)]
c=[list(map(int,input().split())) for _ in range(n)]
a=[[0]*C for _ in range(3)]
for i in range(n):
	for j in range(n):
		a[(i+j)%3][c[i][j]-1]+=1
ans=10**9
for v in permutations(range(C),3):
	tmp=0
	for i in range(3):
		for j in range(C):
			tmp+=a[i][j]*d[j][v[i]]
	ans=min(ans,tmp)
print(ans)
N,M=map(int,input().split())
A=list(map(int,input().split()))
match=[0,2,5,5,4,5,6,3,7,6]
make=dict()
for a in A:
    make[a]=match[a]
dp=[-1]*(N+1)
dp[0]=0
for k in range(1,1+N):
    for d,m in make.items():
        if k-m<0 or dp[k-m]==-1:continue
        dp[k]=max(dp[k],dp[k-m]+1)
        
ans=''
now=N
for k in range(dp[N]):
    res=(0,0)
    for d,m in make.items():
        if dp[now-m]+1==dp[now] and res[0]<d:
            res=(d,m)
    ans+=str(res[0])
    now-=res[1]
print(int(ans))

### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
match=[0,2,5,5,4,5,6,3,7,6]
make=dict()
for a in A:
    make[a]=match[a]
dp=[-1]*(N+1)
dp[0]=0
for k in range(1,1+N):
    for d,m in make.items():
        if k-m<0 or dp[k-m]==-1:continue
        dp[k]=max(dp[k],dp[k-m]+1)
        
ans=''
now=N
for k in range(dp[N]):
    res=(0,0)
    for d,m in make.items():
        if now-m<0:continue
        if dp[now-m]+1==dp[now] and res[0]<d:
            res=(d,m)
    ans+=str(res[0])
    now-=res[1]
print(int(ans))
N,M = map(int,input().split())
A = list(map(int,input().split()))

ans = 0

for i in range(N):
  if A[i] >= 1/4*M:
    ans += 1
  else:
    pass
  
  
  

if ans >= M:
  print('Yes')
  
else:
  print('No')
  
  


### FIXED CODE ###

X,Y,Z= map(int,input().split())

print(Z,X,Y)
def popcount(n):
    cnt = 0
    for i in range(n):
        if ((n >> i) & 1):
            cnt +=1
    return cnt

def f(n):
    cnt = 1
    while True:
        if n == 0:
            break
        n = n % popcount(n)
        cnt += 1
    return cnt

def pow_r(x, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        return pow_r(x ** 2, n // 2)
    else:
        return x * pow_r(x ** 2, (n - 1) // 2)

if __name__ == "__main__":
    n = int(input())
    x = input()
    xList = list(x)
    k = len(xList) - 1
    xNum = int("".join(xList), 2)
    numcnt = popcount(xNum)
    a = numcnt
    wk = 0
    for i in range(n):
        if xList[i] == '0':
            numcnt += 1
        else:
            numcnt -= 1
        xList[i] = str(int(xList[i]) ^ 1)
        xNum = int("".join(xList), 2)
        wk = xNum % numcnt
        if wk == 0:
            print(1)
        else:
            print(f(wk))
        xList[i] = str(int(xList[i]) ^ 1)
        numcnt = a


### FIXED CODE ###

l, r, d = map(int, input().split())
cnt = 0
a = l
while True:
    if a % d == 0:
        break
    else:
        a += 1
while True:
    if a > r:
        break
    cnt += 1
    a += d
print(cnt)
n, q = map(int, input().split())
G = [[] for _ in range(n)]
S = [0] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
for i in range(q):
    p, x = map(int, input().split())
    S[p - 1] += x

ans = [-1] * n

def dfs(v, cnt):
    ans[v] = cnt + S[v]
    for i in G[v]:
        if ans[i] == -1: dfs(i, cnt + S[v])

dfs(0, 0)
print(*ans)

### FIXED CODE ###

from collections import deque

n, q = map(int, input().split())
G = [deque([]) for _ in range(n)]
S = [0] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
for i in range(q):
    p, x = map(int, input().split())
    S[p - 1] += x

ans = [-1] * n

def dfs(v):
    ans[v] = S[v]
    stack = [v]
    while stack:
        x = stack[-1]
        if len(G[x]) > 0:
            w = G[x].popleft()
            if ans[w] == -1:
                ans[w] = ans[x] + S[w]
                stack.append(w)
        else: stack.pop()

dfs(0)
print(*ans)
import collections

N = int(input())
#s = [0,]*(N-1)
s = []
for i in range(N-1):
    #s[i] = int(input())
    s.append(int(input()))

ct = collections.Counter(s)

for i in range(N):
    print(ct[i+1])


### FIXED CODE ###

import collections

N = int(input())
s = list(map(int, input().split()))

ct = collections.Counter(s)

for i in range(N):
    print(ct[i+1])
az = ["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"]
sum_az = [0 for x in range(26)]

while True:
    if not x:
        break
    x = raw_input()
    x.lower()
    for i in range(26):
        for j in range(len(x)):
            if x[j] == az[i]:
                sum_az[i] += 1


for i in range(26):
    print ("%s : %d" % (az[i], sum_az[i]))
                

### FIXED CODE ###

import sys
az =["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"]
sum_az = [0 for x in range(26)]

for x in sys.stdin.read().lower():
    for i in range(26):
        if x == az[i]:
            sum_az[i] += 1


for i in range(26):
    print ("%s : %d" % (az[i], sum_az[i]))
n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()

win_choice = {'s':'r', 'p':'s', 'r':'p'}
janken_point = {'r':r, 's':s, 'p':p}

# a: 相手の手, x:自分が出せない手
def point(a, x=None):
    if x == win_choice[a]: return 0
    else: return janken_point[win_choice[a]]

def total_score(i, cnt, x=None):
    if cnt == 0:
        return 0
    else:
        a = t[(cnt - 1) * k + i]
        choice = win_choice[a]
        return max(point(a, x) + total_score(i, cnt - 1, choice), total_score(i, cnt - 1))

r = [0] * k
for i in range(n):
    i = i % k
    r[i] += 1

score = 0
for i in range(k):
    cnt = r[i]
    score += total_score(i, cnt)

print(score)

### FIXED CODE ###

import sys

n, k = map(int, input().split())
r, s, p = map(int, input().split())
t = input()

win_choice = {'s':'r', 'p':'s', 'r':'p'}
janken_point = {'r':r, 's':s, 'p':p}

dp = []
# a: 相手の手, x:自分が出せない手
def point(a, x=None):
    if x == win_choice[a]: return 0
    else: return janken_point[win_choice[a]]

score = 0
flag = [('0', 1)] * k
for i in range(n):
    if flag[i % k][0] != t[i]:
        score += point(t[i])
        flag[i % k] = (t[i], -1)
    elif flag[i % k][0] == t[i] and flag[i % k][1] == 1:
        score += point(t[i])
        flag[i % k] = (t[i], -1)
    else:
        flag[i % k] = (t[i], 1)

print(score)
n = input()

for i in range(len(n)):
    if n[i] == '1':
        n[i] = '9'
    else:
        n[i] = '1'

print(n)


### FIXED CODE ###

n = input()
m = []

for i in range(len(n)):
    if n[i] == "1":
        m.append(9)
    else:
        m.append(1)
for i in m:
    print(i, end = '')
N , L= map(int,input().split())
lst = list()
lst2 = ''
for i in range(L):
    lst.append(input())
for k  in range(N):
    for j in range(N-1):
        if lst[j] > lst[j+1]:
            lst[j],lst[j+1] = lst[j+1] ,lst[j]

for M in range(L):
    lst2 += lst[M]
print(lst2)


### FIXED CODE ###

N,L=map(int, input().split())
S=[]
for i in range(N):
    S.append(input())
S.sort()
result=''
for j in range(N):
    result+=S[j]     
print(result)
A, B = map(int, input().split())
print (a*b)

### FIXED CODE ###

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

print(A * B)
while True:
    a,b,c = map(int,input().split())
    if a == b == c == -1: break
    if a+b>=80: print('A')
    elif 65 <= a+b < 80: print('B')
    elif 50 <= a+b < 65: print('C')
    elif 30 <= a+b < 50:
        if r<=50: print('C')
        else:     print('D')
    elif a+b<30: print('F')
    



### FIXED CODE ###

while True:
    a,b,c = map(int,input().split())
    if a == b == c == -1: break
    if a==-1 or b==-1:
        print('F')
        continue
    if 80 <= a+b:
        print('A')
        continue
    elif 65 <= a+b:
        print('B')
        continue
    elif 50 <= a+b:
        print('C')
        continue
    elif 30 <= a+b:
        if 50 <= c:
            print('C')
            continue
        else:
            print('D')
            continue
    elif a+b<30: print('F')
N = int(input())
ans = {}
for i in range(len(L)):
    a = input()
    ans[a] = ans.get(a,0) + 1

ans2 = [k for k, v in ans.items() if v == max(ans.values())]
ans2.sort()
[print(i) for i in ans2]


### FIXED CODE ###

A, B, C = map(int, input().split())
if (A ==B and A !=C) or (B == C and A != B) or (A == C and A!=B):
    print('Yes')
else:
    print('No')
N, M = [int(i) for i in input().split()]

dp = [0] * (N + 1)
dp[0] = 1
b = 1
f = False
for _ in range(M):
    a = int(input())
    if a - b == 1:
        f = True
        break
    dp[a] = -1
    b = a

if f:
    ans = 0
else:
    MOD = 10**9 + 7
    
    if dp[1] != -1:
        dp[1] = 1
    for i in range(2, N + 1):
        if dp[i] != -1:
            s = 0 if dp[i-2] == -1 else (dp[i-2] % MOD)

            p = 0 if dp[i-1] == -1 else (dp[i-1] % MOD)

            dp[i] = s + p
            ans = dp[-1] % MOD
print(ans)

### FIXED CODE ###

N, M = [int(i) for i in input().split()]

dp = [0] * (N + 1)
dp[0] = 1
b = 1
f = False
for _ in range(M):
    a = int(input())
    if a - b == 1:
        f = True
        break
    dp[a] = -1
    b = a

if f:
    ans = 0
elif len(dp) == 2:
    if dp[1] == -1:
        ans = 0
    else:
        ans = 1
else:
    MOD = 10**9 + 7
    
    if dp[1] != -1:
        dp[1] = 1
    for i in range(2, N + 1):
        if dp[i] != -1:
            s = 0 if dp[i-2] == -1 else (dp[i-2] % MOD)
            p = 0 if dp[i-1] == -1 else (dp[i-1] % MOD)
            dp[i] = s + p
            ans = dp[-1] % MOD
print(ans)
l = list(map(int,input().split()))
a = l.pop(min(l))
b = l.pop(min(l))
print(a+b)

### FIXED CODE ###

l = list(map(int,input().split()))
a = l.pop(l.index(min(l)))
b = l.pop(l.index(min(l)))
print(a+b)
import math

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

N = int(input())
a = [input() for _ in range(N)]

d = dict()
for x in a:
  s = ''.join(sorted(x))
  if s not in d.keys():
    d[s] = 1
  else:
    d[s] += 1

print(sum([comb(i, 2) for i in d.values()]))

### FIXED CODE ###

from scipy.special import comb
N = int(input())
a = [input() for _ in range(N)]

d = dict()
for x in a:
  s = ''.join(sorted(x))
  if s not in d.keys():
    d[s] = 1
  else:
    d[s] += 1

print(sum([comb(i, 2, exact=True) for i in d.values()]))
import sys
from itertools import combinations
import bisect
import math
n = int(input())
l_ls = [int(i) for i in sys.stdin.readline().split()]
l_ls.sort()
#l_dict = { i : j for i, j in enumerate(l_ls)}
_sum_ls = []
cnt = 0
for combi in combinations(l_ls, 2):
    _sum = combi[0] + combi[1]
    ind = bisect.bisect_left(l_ls, _sum)
    cnt += n - ind
print(int(math.factorial(n) / math.factorial(3) / math.factorial(n-3)) - cnt)

### FIXED CODE ###

import sys
from itertools import combinations
import bisect
import math
n = int(input())
l_ls = [int(i) for i in sys.stdin.readline().split()]
l_ls.sort()
cnt = 0
for a, b in combinations(l_ls, 2):
    _sum = a + b
    ind = bisect.bisect_left(l_ls, _sum)
    cnt += n - ind
print(int(math.factorial(n) // math.factorial(3) // math.factorial(n-3)) - cnt)
N,T=map(int,input().split())
s=[]
o=[]
for i in range(N):
  c,t=map(int,input().split())
  if t<=T:
    s.append(c)
  else:
    o.append(c)
if len(o)==N:
  print(TLE)
else:
  print(min(s))


### FIXED CODE ###

N,T=map(int,input().split())
s=[]
o=[]
for i in range(N):
  c,t=map(int,input().split())
  if t<=T:
    s.append(c)
  else:
    o.append(c)
if len(o)==N:
  print("TLE")
else:
  print(min(s))
n, m = map(int, input().split())
ans = [-1 for _ in range(n)]
end_flag = False
for _ in range(m):
    s, c = map(int, input().split())
    if ans[s-1] == -1:
        ans[s-1] = c
    elif ans[s-1] == c:
        continue
    else:
        end_flag = True
        break
# print(ans)
if ans[0] == 0:
    end_flag = True
if ans[0] == -1:
    ans[0] = 1
if ans[1] == -1:
    ans[1] = 0
if ans[2] == -1:
    ans[2] = 0
# print(ans)
if end_flag:
    print(-1)
else:
    print('{}{}{}'.format(ans[0], ans[1], ans[2]))


### FIXED CODE ###

n, m = map(int, input().split())
ans = [-1 for _ in range(n)]
end_flag = False
for _ in range(m):
    s, c = map(int, input().split())
    if ans[s-1] == -1:
        ans[s-1] = c
    elif ans[s-1] == c:
        continue
    else:
        end_flag = True
        break
# print(ans)
if ans[0] == 0 and n > 1:
    end_flag = True
if ans[0] == -1:
    if n > 1:
        ans[0] = 1
    else:
        ans[0] = 0

for i in range(1, n):
    if ans[i] == -1:
        ans[i] = 0
# print(ans)
if end_flag:
    print(-1)
else:
    ss = ''
    for i in ans:
        ss = ss + str(i)
    print(ss)
A_list = []

N = int(input())
A = input()
A_list = A.split(' ')

for n in range(N):
    if (int(A_list[n]) % 2 == 0):
        if (int(A_list[n]) % 3 == 0) | (int(A_list[n]) % 5 == 0):
            ans = 'APPROVED'
        else:
            ans = 'DENIED'
            break
print(ans)

### FIXED CODE ###

A_list = []
ans = 0

N = int(input())
A = input()
A_list = A.split(' ')

for n in range(N):
    if (int(A_list[n]) % 2 == 0):
        if (int(A_list[n]) % 3 == 0) | (int(A_list[n]) % 5 == 0):
            ans = ans + 0
        else:
            ans = ans + 1
if ans == 0:
    print('APPROVED')
else:
    print('DENIED')
a, b = map(int, raw_input().split())

if a > b:
	print "a > b"
elif a < b:
	print "a < b"
else
	print "a == b"

### FIXED CODE ###

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

if a > b:
	print 'a > b'
elif a < b:
	print 'a < b'
else:
	print 'a == b'
import sys
sys.setrecursionlimit(10 ** 6)  # 変更

from bisect import bisect_left,bisect
n = int(input())
x = list(map(int,input().split()))
t = (n-1).bit_length()
kprv = [[10**10 for i in range(t)] for j in range(n-1)]
for i in range(t):
    for j in range(n):
        if j + pow(2,i) > n-1:
            break
        kprv[j][i] = x[j+2**i] - x[j]

L = int(input())
q = int(input())

for _ in range(q):
    a , b = map(lambda x:int(x)-1,input().split())
    cou = 0
    if a > b:
        a , b = b , a
    now = a
    while now < b:
        cou += 1
        p = L
        while True:
            nex = bisect(kprv[now],p)
            if nex == 0:
                break
            else:
                p -= kprv[now][nex-1]
                now += pow(2,nex-1)
    print(cou)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 変更
from bisect import bisect_left,bisect

n = int(input())
x = list(map(int,input().split()))
L = int(input())
t = n.bit_length()
prv = [n-1] * n
for i in range(n):
    prv[i] = bisect(x,x[i]+L) - 1
kprv = [prv]
S = prv
for i in range(t-1):
    kar = [n-1] * n
    for j in range(n):
        kar[j] = S[S[j]]
    kprv.append(kar)
    S = kar

q = int(input())
for _ in range(q):
    a , b = map(lambda x:int(x)-1,input().split())
    if a > b:
        a , b = b , a
    lef = 0
    rig = n-1
    while rig - lef > 1:
        mid = (rig+lef)//2
        p = mid.bit_length()
        now = a
        for i in range(p):
            if (mid>>i) & 1 == 1:
                now = kprv[i][now]
        if now >= b:
            rig = mid
        elif now < b:
            lef = mid
    print(rig)
x = int(input())

count = 0
for i in range(0, x):
    a =  int(input())
    for j in range ( 2,  a ):
        if a % j == 0:
             count += 1
	if j * j > a
             break;
        
print(x-count)
        



### FIXED CODE ###

x = int(input())

count = 0
for i in range(0, x):
    a =  int(input())
    for j in range ( 2,  a ):
        c = int(a)
        if a % j == 0:
            count += 1
            break;
        if j * j  > c:
            break;
        
print(x-count)
n = int(input())
s = input()
r = s.count('R')
g = s.count('G')
b = s.count('B')
ans = r*g*b
for i in range(n-2):
    for j in range(i+1, n-1):
        k = 2j - i
        if k >= n:
            break 
        if s[i]!=s[j] and s[k]!= s[i] and s[j]!=s[k]:
            ans -= 1
print(ans)


### FIXED CODE ###

n = int(input())
s = input()
r = s.count('R')
g = s.count('G')
b = s.count('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:
            break 
        if s[i]!=s[j] and s[k]!= s[i] and s[j]!=s[k]:
            ans -= 1
print(ans)
#coding:utf-8

import sys
import copy

def main():
    line = sys.stdin.readline()
    #case
    while line.split() != ["0","0"]:
        analy(line)
        line = sys.stdin.readline()
    return

def analy(line):
    #t
    field = [int(n) for n in line.split()]
    # *&
    num = int(sys.stdin.readline())
    data = []
    for i in range(num):
        a = sys.stdin.readline()
        b = [int(n) for n in a.split()]
        #*&
        data.append(b)
    print (compute(field, data))

def compute(field, ng):
    list = []
    for i in range(field[1]):
        for j in range(field[0]):
            #*?&k??WfDO
                if i == 0 :
                    #j
                    if [j+1,i+1] in ng:
                        list.append(0)
                    elif j == 0:
                        #?LjD
                        list.append(1)
                    else:
                        list.append(list[j-1])
                else:
                    if [j+1,i+1] in ng:
                        list[j] = 0
                    elif j != 0:
                    #no left >> the same.
                        list[j] = list[j-1] + list[j]
    return list[len(list)-1]

if __name__ == "__main__":
    main()

### FIXED CODE ###

#coding:utf-8
  
import sys
import copy
  
def main():
    line = sys.stdin.readline()
    #case
    while line.split() != ["0","0"]:
        analy(line)
        line = sys.stdin.readline()
    return
  
def analy(line):
    #????
    field = [int(n) for n in line.split()]
    # ???A?c
    num = int(sys.stdin.readline())
    data = []
    for i in range(num):
        a = sys.stdin.readline()
        b = [int(n) for n in a.split()]
        #???A?c
        data.append(b)
    print (compute(field, data))
  
def compute(field, ng):
    list = []
    for i in range(field[1]):
        for j in range(field[0]):
            #???¨?c???????????¢??
                if i == 0 :
                    #??????
                    if [j+1,i+1] in ng:
                        list.append(0)
                    elif j == 0:
                        #?¶?????¢
                        list.append(1)
                    else:
                        list.append(list[j-1])
                else:
                    if [j+1,i+1] in ng:
                        list[j] = 0
                    elif j != 0:
                    #no left >> the same.
                        list[j] = list[j-1] + list[j]
    return list[len(list)-1]
  
if __name__ == "__main__":
    main()
# -*- coding: utf-8 -*-

# input
S = str(input())
# S = "abcdefghijklmnopqrstuvwzyx"

s = list(S)
ss = []
for i in range(len(s)):
    ss.append(ord(s[i]))
a = list(ss)

t = [chr(i) for i in range(97, 97+26)]
tt = [i for i in range(97, 97+26)]
b = list(tt)


def func(s_):
    ss_ = []
    for i in range(len(s_)):
        ss_.append(chr(s_[i]))
    ss_ = ''.join(ss_)
    return ss_


# solve
if (len(ss) < 26):
    for i in range(len(s)):
        b.remove(ss[i])
    a.append(min(b))
    print(func(a))

if (len(ss) == 26):
    if (S == "zyxwvutsrqponmlkjihgfedcba"):
        print(-1)
    else:
        for i in range(len(s)):
            if (a[i] == b[i]):
                continue
            else:
                c = a[0:i] + [b[i]]
                break
        print(func(c))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import bisect

# input
S = input()
# S = "abcdefghijklmnopqrstuvwzyx"
# S = "atcoder"
# S = "qpwoeirutyalskdjfhgzmxnvcb"

s = list(S)
a = []
for i in range(len(s)):
    a.append(ord(s[i]))

t = [chr(i) for i in range(97, 97+26)]
b = [i for i in range(97, 97+26)]


# function
def func(s_):
    ss_ = []
    for i in range(len(s_)):
        ss_.append(chr(s_[i]))
    ss_ = ''.join(ss_)
    return ss_


# solve
if (len(s) < 26):
    for i in range(len(s)):
        b.remove(a[i])
    a.append(min(b))
    print(func(a))

if (len(s) == 26):
    for i in reversed(range(len(s))):
        if (a[i] < a[i-1]):
            if (i == 1):
                print(-1)
                break
            else:
                continue
        else:
            c = a[0:i]
            d = a[i:len(a)]
            d = sorted(d)
            # a[i-1]よりも大きくて最も小さいものを探す
            num = c.pop()
            ind = bisect.bisect_left(d, num)
            c.append(d[ind])
            print(func(c))
            break