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
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc= new Scanner(System.in);
		final String finalWord = "zyxwvutsrqponmlkjihgfedcba";
		String word =sc.nextLine();
		String[] words = word.split("");
		int[] exist = new int[26];
		for(int i=0;i<26;i++){
			exist[i]=-1;
		}
		for(int i=0;i<words.length;i++){
			if(words[i].equals("a")){
				exist[0]=i;
			}else if(words[i].equals("b")){
				exist[1]=i;
			}else if(words[i].equals("c")){
				exist[2]=i;
			}else if(words[i].equals("d")){
				exist[3]=i;
			}else if(words[i].equals("e")){
				exist[4]=i;
			}else if(words[i].equals("f")){
				exist[5]=i;
			}else if(words[i].equals("g")){
				exist[6]=i;
			}else if(words[i].equals("h")){
				exist[7]=i;
			}else if(words[i].equals("i")){
				exist[8]=i;
			}else if(words[i].equals("j")){
				exist[9]=i;
			}else if(words[i].equals("k")){
				exist[10]=i;
			}else if(words[i].equals("l")){
				exist[11]=i;
			}else if(words[i].equals("m")){
				exist[12]=i;
			}else if(words[i].equals("n")){
				exist[13]=i;
			}else if(words[i].equals("o")){
				exist[14]=i;
			}else if(words[i].equals("p")){
				exist[15]=i;
			}else if(words[i].equals("q")){
				exist[16]=i;
			}else if(words[i].equals("r")){
				exist[17]=i;
			}else if(words[i].equals("s")){
				exist[18]=i;
			}else if(words[i].equals("t")){
				exist[19]=i;
			}else if(words[i].equals("u")){
				exist[20]=i;
			}else if(words[i].equals("v")){
				exist[21]=i;
			}else if(words[i].equals("w")){
				exist[22]=i;
			}else if(words[i].equals("x")){
				exist[23]=i;
			}else if(words[i].equals("y")){
				exist[24]=i;
			}else if(words[i].equals("z")){
				exist[25]=i;
			}
		}
		if(words.length==26){
			if(word.equals(finalWord)){
				System.out.println(-1);
			}else{
				char[] c = word.toCharArray();
				int point=-1;
				char big=c[25];
				int just=25;
				for(int i=1;i<26;i++){
					if(big>c[25-i]){
						point=25-i;
						break;
					}else{
						big=c[25-i];
						just=25-i;
					}
				}
				for(int i=25;i>point;i--){
					if(c[just]>c[i] && c[i]>c[point]){
						just=i;
					}
				}
				String str="";
				for(int i=0;i<point;i++){
					str=str+words[i];
				}
				str=str+words[just];
				if(point==-1){
					String s="";
					for(int i=0;i<26;i++){
						if(exist[i]==0){
							i=i+1;
							if(i==0){
								s="a";
							}else if(i==1){
								s="b";
							}else if(i==2){
								s="c";
							}else if(i==3){
								s="d";
							}else if(i==4){
								s="e";
							}else if(i==5){
								s="f";
							}else if(i==6){
								s="g";
							}else if(i==7){
								s="h";
							}else if(i==8){
								s="i";
							}else if(i==9){
								s="j";
							}else if(i==10){
								s="k";
							}else if(i==11){
								s="l";
							}else if(i==12){
								s="m";
							}else if(i==13){
								s="n";
							}else if(i==14){
								s="o";
							}else if(i==15){
								s="p";
							}else if(i==16){
								s="q";
							}else if(i==17){
								s="r";
							}else if(i==18){
								s="s";
							}else if(i==19){
								s="t";
							}else if(i==20){
								s="u";
							}else if(i==21){
								s="v";
							}else if(i==22){
								s="w";
							}else if(i==23){
								s="x";
							}else if(i==24){
								s="y";
							}else if(i==25){
								s="z";
							}							
							break;
						}
					}
					
					System.out.println(s);
				}else{System.out.println(str);}
			}
		}else{
			for(int i=0;i<26;i++){
				if(exist[i]==-1){
					String s="";
					if(i==0){
						s="a";
					}else if(i==1){
						s="b";
					}else if(i==2){
						s="c";
					}else if(i==3){
						s="d";
					}else if(i==4){
						s="e";
					}else if(i==5){
						s="f";
					}else if(i==6){
						s="g";
					}else if(i==7){
						s="h";
					}else if(i==8){
						s="i";
					}else if(i==9){
						s="j";
					}else if(i==10){
						s="k";
					}else if(i==11){
						s="l";
					}else if(i==12){
						s="m";
					}else if(i==13){
						s="n";
					}else if(i==14){
						s="o";
					}else if(i==15){
						s="p";
					}else if(i==16){
						s="q";
					}else if(i==17){
						s="r";
					}else if(i==18){
						s="s";
					}else if(i==19){
						s="t";
					}else if(i==20){
						s="u";
					}else if(i==21){
						s="v";
					}else if(i==22){
						s="w";
					}else if(i==23){
						s="x";
					}else if(i==24){
						s="y";
					}else if(i==25){
						s="z";
					}
					word=word+s;
					System.out.println(word);
					break;
				}
			}
		}
		
	}
}
