Problem: You are given a string s consisting of |s| small english letters.

In one move you can replace any character of this string to the next character in alphabetical order (a will be replaced with b, s will be replaced with t, etc.). You cannot replace letter z with any other letter.

Your target is to make some number of moves (not necessary minimal) to get string abcdefghijklmnopqrstuvwxyz (english alphabet) as a subsequence. Subsequence of the string is the string that is obtained by deleting characters at some positions. You need to print the string that will be obtained from the given string and will be contain english alphabet as a subsequence or say that it is impossible.

Input

The only one line of the input consisting of the string s consisting of |s| (1 ≤ |s| ≤ 105) small english letters.

Output

If you can get a string that can be obtained from the given string and will contain english alphabet as a subsequence, print it. Otherwise print «-1» (without quotes).

Examples

Input

aacceeggiikkmmooqqssuuwwyy


Output

abcdefghijklmnopqrstuvwxyz


Input

thereisnoanswer


Output

-1

Solution (in JAVA):

Solution:
			// Code Author: Shrey Shah
			// Institute : DA-IICT
			// Quote : Think twice , Code Once
			 
			import java.io.*;
	
			import java.math.BigInteger;
			import java.math.RoundingMode;
			import java.text.DecimalFormat;
			import java.util.*;
			
			
			public class Tester5 {
			
				static double eps=(double)1e-6;
				static long mod=(int)1e9+7;
				static long d,x,y;
				static long  phi[],sumOfGCD[];
				public static void main(String args[]){
					InputReader sc = new InputReader(System.in);
					OutputStream outputStream = System.out;
					PrintWriter out = new PrintWriter(outputStream);
					//---Code Begins Here--------
					String s = sc.nextLine();
					char a[] = s.toCharArray();
						char c = 'a';
						for(int i=0;i<s.length();i++)
						{
							if(c>'z' || a[i]>c)
								continue;
							a[i]=c++;							
						}
						if(c<='z')
							out.print(-1);
						else
						{
							for(int i=0;i<a.length;i++)
								out.print(a[i]);
						}
					
					//---Code Ends Here----------
					out.close();
				}
				
				private static long C(long l, long vowel_count, long[] fact) {
					long num = fact[(int)l];
					long den = (fact[(int)vowel_count]%mod * fact[(int)(l-vowel_count)]%mod)%mod;
					long inv = modInverse(den,mod);
					return (num%mod * inv%mod)%mod;
					
				}
				private static long cal(int[] a) 
				{
					long max_so_far = Long.MIN_VALUE, max_ending_here = 0,
				    start =0, end = 0, s=0;
						 
					 for (int i=0; i<a.length; i++ )
					 {
						        max_ending_here += a[i];
						 
						        if (max_so_far < max_ending_here)
						        {
						            max_so_far = max_ending_here;
						            start = s;
						            end = i;
						        }
						 
						        if (max_ending_here < 0)
						        {
						            max_ending_here = 0;
						            s = i+1;
						        }
					 }
				return max_so_far;
				}
				private static long fact(long count) {
					long ans=1;
					for(int i=2;i<=count;i++)
						ans*=i;
					return ans;
				}
				static int[] spf(int n)
				{
				    int spf[] = new int[n+1];
				    Arrays.fill(spf,0);
				    spf[1] = 1;
				 
				    for (int i = 2; i <= n; i++)
				    {
				        if (spf[i] == 0)
				        {
				            spf[i] = i;
				            for (int j = 2*i; j <= n; j += i)
				                if (spf[j] == 0)
				                   spf[j] = i;
				            
				        }  
				    }
				    return spf;
				}
				
			    static int[] sieve(int n)
					{
						int prime[] = new int[n+1];
						for(int i=0;i<n;i++)
							prime[i] = 1;
						prime[0]=0;
						prime[1]=0;
						for(int p = 2; p*p <=n; p++)
						{
							// If prime[p] is not changed, then it is a prime
							if(prime[p] == 1)
							{
								// Update all multiples of p
								for(int i = p*2; i <= n; i += p)
									prime[i] = 0;
							}
						
						}
						return prime;
					}
			    
			    
				public static void computeTotient(int n)
				{
				    phi = new long[n+1];
				    for (int i=1; i<=n; i++)
				        phi[i] = i;
				 
				    for (int p=2; p<=n; p++)
				    {
				        // If phi[p] is not computed already,
				        // then number p is prime
				        if (phi[p] == p)
				        {
				            // Phi of a prime number p is
				            // always equal to p-1.
				            phi[p] = p-1;
				 
				            // Update phi values of all
				            // multiples of p
				            for (int i = 2*p; i<=n; i += p)
				            {
				               // Add contribution of p to its
				               // multiple i by multiplying with
				               // (1 - 1/p)
				               phi[i] = (phi[i]/p) * (p-1);
				            }
				        }
				    }
				}
				public static void sumOfGcdPairs(int MAX)
				{
				    computeTotient(MAX);
				    sumOfGCD = new long[MAX];
				    for (int i=1; i<MAX; ++i)
				    {
				        // Iterate throght all the divisors
				        // of i.
				        for (int j=2; i*j<MAX; ++j)
				        	 sumOfGCD[i*j] += i*phi[j];
				    }
				 
				    for (int i=2; i<MAX; i++)
				    	 sumOfGCD[i] +=  sumOfGCD[i-1];
				}
				
				static long modInverse(long A, long M)
				{
					if(gcd(A,M)!=1)
						return -1;
				    extendedEuclid(A,M);
				    return (x%M+M)%M;    //x may be negative
				}
				static void extendedEuclid(long A, long B) {
				    if(B == 0) {
				        d = A;
				        x = 1;
				        y = 0;
				    }
				    else {
				        extendedEuclid(B, A%B);
				        long temp = x;
				        x = y;
				        y = temp - (A/B)*y;
				    }
				}
		
				static int power(int x,int n)
				{
				    if(n==0)
				        return 1;
				    else if(n%2 == 0)        //n is even
				        return power(x*x,n/2);
				    else                             //n is odd
				        return x*power(x*x,(n-1)/2);
				}
				 static long ce(long x)
					{
						if(x%2!=0)
							return x/2+1;
						return x/2;
					}
				static boolean isSubSequence(String str1, String str2, int m, int n)
				{
				   int j = 0;
				   for (int i=0; i<n&&j<m; i++)
				       if (str1.charAt(j) == str2.charAt(i))
				         j++;
				 
				   return (j==m);
				}
					
				static long fibo(long l) {
			        if (l < 0) {
			            throw new IllegalArgumentException("The fibo value cannot be negative");
			        }
			
			        if (l <= 1) return l;
			
			        long[][] result = {{1, 0}, {0, 1}}; // identity matrix.
			        long[][] fiboM = {{1, 1}, {1, 0}};
			
			        while (l > 0) {
			            if (l%2 == 1) {
			                multMatrix(result, fiboM);
			            }
			            l = l / 2;
			            multMatrix(fiboM, fiboM);
			        }
			
			        return result[1][0];
			    }
			
			    private static void multMatrix(long[][] result, long[][] fiboM) {
			        long a = (result[0][0]%mod * fiboM[0][0]%mod)%mod +  (result[0][1]%mod * fiboM[1][0]%mod)%mod;
			        long b = (result[0][0]%mod * fiboM[0][1]%mod)%mod + ( result[0][1]%mod * fiboM[1][1]%mod)%mod;
			        long c = (result[1][0]%mod * fiboM[0][0]%mod)%mod + ( result[1][1]%mod * fiboM[0][1]%mod)%mod;
			        long d = (result[1][0]%mod * fiboM[0][1]%mod)%mod +  (result[1][1]%mod * fiboM[1][1]%mod)%mod;
			
			        result[0][0] = a;
			        result[0][1] = b;
			        result[1][0] = c;
			        result[1][1] = d;
			    }
			    
			    
				static boolean isPal(String s)
				{
					for(int i=0, j=s.length()-1;i<=j;i++,j--)
					{
						if(s.charAt(i)!=s.charAt(j)) return false;
					}
					return true;
				}
				public static String rev(String s)
				{
					StringBuilder sb=new StringBuilder(s);
					sb.reverse();
					return sb.toString();
				}
				    
				static long lcm(long a, long b)
				{
				    return a * (b / gcd(a, b));
				}
				
				static long gcd(long a, long b)
				{
				    while (b > 0)
				    {
				        long temp = b;
				        b = a % b; // % is remainder
				        a = temp;
				    }
				    return a;
				}
				static long modulo(long a,long b,long c) {
					long x=1;
					long y=a;
					while(b > 0){
						if(b%2 == 1){
							x=(x*y)%c;
						}
						y = (y*y)%c; // squaring the base
						b /= 2;
					}
					return  x%c;
				}
				
				static int mergeSort(int arr[], int array_size)
			    {
			        int temp[] = new int[array_size];
			        return _mergeSort(arr, temp, 0, array_size - 1);
			    }
			      
			    /* An auxiliary recursive method that sorts the input array and
			      returns the number of inversions in the array. */
			    static int _mergeSort(int arr[], int temp[], int left, int right)
			    {
			      int mid, inv_count = 0;
			      if (right > left)
			      {
			        /* Divide the array into two parts and call _mergeSortAndCountInv()
			           for each of the parts */
			        mid = (right + left)/2;
			      
			        /* Inversion count will be sum of inversions in left-part, right-part
			          and number of inversions in merging */
			        inv_count  = _mergeSort(arr, temp, left, mid);
			        inv_count += _mergeSort(arr, temp, mid+1, right);
			      
			        /*Merge the two parts*/
			        inv_count += merge(arr, temp, left, mid+1, right);
			      }
			      return inv_count;
			    }
			      
			    /* This method merges two sorted arrays and returns inversion count in
			       the arrays.*/
			    static int merge(int arr[], int temp[], int left, int mid, int right)
			    {
			      int i, j, k;
			      int inv_count = 0;
			      
			      i = left; /* i is index for left subarray*/
			      j = mid;  /* j is index for right subarray*/
			      k = left; /* k is index for resultant merged subarray*/
			      while ((i <= mid - 1) && (j <= right))
			      {
			        if (arr[i] <= arr[j])
			        {
			          temp[k++] = arr[i++];
			        }
			        else
			        {
			          temp[k++] = arr[j++];
			      
			         /*this is tricky -- see above explanation/diagram for merge()*/
			          inv_count = inv_count + (mid - i);
			        }
			      }
			      
			      /* Copy the remaining elements of left subarray
			       (if there are any) to temp*/
			      while (i <= mid - 1)
			        temp[k++] = arr[i++];
			      
			      /* Copy the remaining elements of right subarray
			       (if there are any) to temp*/
			      while (j <= right)
			        temp[k++] = arr[j++];
			      
			      /*Copy back the merged elements to original array*/
			      for (i=left; i <= right; i++)
			        arr[i] = temp[i];
			      
			      return inv_count;
			    }
				
				
				
				
				public static void debug(Object... o) {
					System.out.println(Arrays.deepToString(o));
				}
				static class Pair implements Comparable<Pair>{
					long x;
					long y;
					Pair(long k,long count){
						x=k;
						y=count;
					}
					@Override
					public int compareTo(Pair o) {
						if(this.y>o.y)
							return 1;
						if(this.y<o.y)
							return -1;
						
						return 0;
					}
				}
			
				static class InputReader {
					public BufferedReader reader;
					public StringTokenizer tokenizer;
			
					public InputReader(InputStream inputstream) {
						reader = new BufferedReader(new InputStreamReader(inputstream));
						tokenizer = null;
					}
			
					public String nextLine(){
						String fullLine=null;
						while (tokenizer == null || !tokenizer.hasMoreTokens()) {
							try {
								fullLine=reader.readLine();
							} catch (IOException e) {
								throw new RuntimeException(e);
							}
							return fullLine;
						}
						return fullLine;
					}
					public String next() {
						while (tokenizer == null || !tokenizer.hasMoreTokens()) {
							try {
								tokenizer = new StringTokenizer(reader.readLine());
							} catch (IOException e) {
								throw new RuntimeException(e);
							}
						}
						return tokenizer.nextToken();
					}
					public long nextLong() {
						return Long.parseLong(next());
					}
					public int nextInt() {
						return Integer.parseInt(next());
					}
				}
				
			}
		
			class SegmentTree
			{
				static int segTree[],low,high,pos;
				public SegmentTree(int len)
				{
					int x = (int) (Math.ceil(Math.log(len) / Math.log(2)));
				    int max_size = 2 * (int) Math.pow(2, x) - 1;
				    segTree = new int[max_size];
				}
				
				
				public static void construct(int a[])
				{
					constructUtil(segTree,a,0,a.length-1,0);
				}
				
				public static void constructUtil(int segTree[] , int input[] ,int low,int high,int pos)
				{
					if(low==high)
					{
						segTree[pos]=input[low];
						return;
					}
					int mid = low + (high-low)/2;
					constructUtil(segTree,input,low,mid,2*pos+1);
					constructUtil(segTree,input,mid+1,high,2*pos+2);
					segTree[pos] = Math.min(segTree[2*pos+1], segTree[2*pos+2]);
				}
				
				public static int rangeQuery(int a[],int start,int end)
				{
					return rangeQueryUtil(segTree,start,end,0,a.length-1,0);
				}
				
				public static int rangeQueryUtil(int segTree[] , int qlow,int qhigh,int low,int high,int pos)
				{
					if(qlow<=low && qhigh>=high)
						return segTree[pos];
					if(qlow>high || qhigh<low)
						return Integer.MAX_VALUE;
					int mid = low + (high-low)/2;
					return Math.min(rangeQueryUtil(segTree,qlow,qhigh,low,mid,2*pos+1), 
							rangeQueryUtil(segTree,qlow,qhigh,mid+1,high,2*pos+2));
				}
			}