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:

/**
 * Date: 06 Mar, 2018
 * Link :
 *
 * @author Prasad-Chaudhari
 * @email prasadc8897@gmail.com
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class New_File_4 {

    public static void main (String[] args) throws java.lang.Exception {
        FastIO2 in = new FastIO2();
        String s =in.next();
        char[] c = s.toCharArray();
        int count=25;
        for(int i=c.length-1;i>=0&&count>=0;i--){
            if(c[i]<='a'+count){
                c[i]=(char)('a'+count);
                count--;
            }
        }
        if(count>=0){
            System.out.println(-1);
        }
        else{
            for(int i=0;i<c.length;i++){
                System.out.print(c[i]);
            }
        }
        // if(lcs(c,"abcdefghijklmnopqrstuvwxyz".toCharArray(),c.length,26)==26){
        //     for(int i=0;i<c.length;i++){
        //         System.out.print(c[i]);
        //     }
        // }
        // else{
        //     System.out.println(-1);
        // }
    }
    static int lcs( char[] X, char[] Y, int m, int n )
      {
        int L[][] = new int[m+1][n+1];

        /* Following steps build L[m+1][n+1] in bottom up fashion. Note
             that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1] */
        for (int i=0; i<=m; i++)
        {
          for (int j=0; j<=n; j++)
          {
            if (i == 0 || j == 0)
                L[i][j] = 0;
            else if (X[i-1] <= Y[j-1]){
                X[i-1] = Y[j-1];
                L[i][j] = L[i-1][j-1] + 1;
            }
            else
                L[i][j] = max(L[i-1][j], L[i][j-1]);
          }
        }
      int index = L[m][n];
        int temp = index;

        // Create a character array to store the lcs string
        char[] lcs = new char[index+1];
        lcs[index] = '\0'; // Set the terminating character

        // Start from the right-most-bottom-most corner and
        // one by one store characters in lcs[]
        int i = m, j = n;
        while (i > 0 && j > 0)
        {
            // If current character in X[] and Y are same, then
            // current character is part of LCS
            if (X[i-1] <= Y[j-1])
            {
                // Put current character in result
                X[i-1] = Y[j-1];

                // reduce values of i, j and index
                i--;
                j--;
                index--;
            }

            // If not same, then find the larger of two and
            // go in the direction of larger value
            else if (L[i-1][j] > L[i][j-1])
                i--;
            else
                j--;
        }
        return temp;
      }

      /* Utility function to get max of 2 integers */
    static int max(int a, int b)
    {
        return (a > b)? a : b;
    }

    static class FastIO2 {

        private final BufferedReader br;
        private String s[];
        private int index;

        public FastIO2() throws IOException {
            br = new BufferedReader(new InputStreamReader(System.in));
            index = 0;
        }

        public int ni() throws IOException {
            return Integer.parseInt(nextToken());
        }

        public double nd() throws IOException {
            return Double.parseDouble(nextToken());
        }

        public long nl() throws IOException {
            return Long.parseLong(nextToken());
        }

        public String next() throws IOException {
            return nextToken();
        }

        public String nli() throws IOException {
            return br.readLine();
        }

        public int[] gia(int n) throws IOException {
            int a[] = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }

        public int[] gia(int n, int start, int end) throws IOException {
            validate(n, start, end);
            int a[] = new int[n];
            for (int i = start; i < end; i++) {
                a[i] = ni();
            }
            return a;
        }

        public double[] gda(int n) throws IOException {
            double a[] = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }

        public double[] gda(int n, int start, int end) throws IOException {
            validate(n, start, end);
            double a[] = new double[n];
            for (int i = start; i < end; i++) {
                a[i] = nd();
            }
            return a;
        }

        public long[] gla(int n) throws IOException {
            long a[] = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }

        public long[] gla(int n, int start, int end) throws IOException {
            validate(n, start, end);
            long a[] = new long[n];
            for (int i = start; i < end; i++) {
                a[i] = ni();
            }
            return a;
        }

        private String nextToken() throws IndexOutOfBoundsException, IOException {
            if(s == null){
                s = br.readLine().split(" ");
            }
            if (index == s.length) {
                s = br.readLine().split(" ");
                index = 0;
            }
            return s[index++];
        }

        private void validate(int n, int start, int end) {
            if (start < 0 || end >= n) {
                throw new IllegalArgumentException();
            }
        }
    }
}