Gotou just received a dictionary. However, he doesn't recognize the language used in the dictionary. He did some analysis on the dictionary and realizes that the dictionary contains all possible diverse words in lexicographical order.

A word is called diverse if and only if it is a nonempty string of English lowercase letters and all letters in the word are distinct. For example, `atcoder`, `zscoder` and `agc` are diverse words while `gotou` and `connect` aren't diverse words.

Given a diverse word S, determine the next word that appears after S in the dictionary, i.e. the lexicographically smallest diverse word that is lexicographically larger than S, or determine that it doesn't exist.

Let X = x_{1}x_{2}...x_{n} and Y = y_{1}y_{2}...y_{m} be two distinct strings. X is lexicographically larger than Y if and only if Y is a prefix of X or x_{j} > y_{j} where j is the smallest integer such that x_{j} \neq y_{j}.

Constraints

* 1 \leq |S| \leq 26
* S is a diverse word.

Input

Input is given from Standard Input in the following format:


S


Output

Print the next word that appears after S in the dictionary, or `-1` if it doesn't exist.

Examples

Input

atcoder


Output

atcoderb


Input

abc


Output

abcd


Input

zyxwvutsrqponmlkjihgfedcba


Output

-1


Input

abcdefghijklmnopqrstuvwzyx


Output

abcdefghijklmnopqrstuvx



def alphabet_to_int(c):
    if c=="a":
        return 0
    elif c=="b":
        return 1
    elif c=="c":
        return 2
    elif c=="d":
        return 3
    elif c=="e":
        return 4
    elif c=="f":
        return 5
    elif c=="g":
        return 6
    elif c=="h":
        return 7
    elif c=="i":
        return 8
    elif c=="j":
        return 9
    elif c=="k":
        return 10
    elif c=="l":
        return 11
    elif c=="m":
        return 12        
    elif c=="n":
        return 13
    elif c=="o":
        return 14
    elif c=="p":
        return 15
    elif c=="q":
        return 16
    elif c=="r":
        return 17
    elif c=="s":
        return 18
    elif c=="t":
        return 19
    elif c=="u":
        return 20
    elif c=="v":
        return 21
    elif c=="w":
        return 22
    elif c=="x":
        return 23
    elif c=="y":
        return 24              
    elif c=="z":
        return 25        
        
def int_to_alphabet(i):
    if i==0:
        return "a"
    elif i==1:
        return "b"
    elif i==2:
        return "c"
    elif i==3:
        return "d"
    elif i==4:
        return "e"
    elif i==5:
        return "f"
    elif i==6:
        return "g"
    elif i==7:
        return "h"
    elif i==8:
        return "i"
    elif i==9:
        return "j"
    elif i==10:
        return "k"
    elif i==11:
        return "l"
    elif i==12:
        return "m"        
    elif i==13:
        return "n"
    elif i==14:
        return "o"
    elif i==15:
        return "p"
    elif i==16:
        return "q"
    elif i==17:
        return "r"
    elif i==18:
        return "s"
    elif i==19:
        return "t"
    elif i==20:
        return "u"
    elif i==21:
        return "v"
    elif i==22:
        return "w"
    elif i==23:
        return "x"
    elif i==24:
        return "y"              
    elif i==25:
        return "z"        
            
        
S=raw_input()

if len(S)<=25:
    char_set = [0 for i in range(26)]
    for i in range(len(S)):
        char_set[alphabet_to_int(S[i])]=1
    for i in range(26):
        if char_set[i]==0:
            ans=S+int_to_alphabet(i)
            print ans
            break
else:
    prev_char=S[-1]
    prev_set = [0 for i in range(26)]
    prev_set[alphabet_to_int(prev_char)]=1
    for i in range(26):
        if alphabet_to_int(prev_char)>alphabet_to_int(S[-(i+1)]):
            for j in range(alphabet_to_int(S[-(i+1)]),26):
                if prev_set[j] == 1:
                        ans=S[:-(i+1)]+int_to_alphabet(j)
                        break
            print ans
            break
        if i==25:
            print -1
        prev_set[alphabet_to_int(S[-(i+1)])]=1
        prev_char=S[-(i+1)]
