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:
import java.io.*;
import java.util.*;
import java.math.*;
import java.lang.*;

import static java.lang.Math.*;

public class c implements Runnable {

    long mod = 1000000000 +7;
    InputReader read = new InputReader(System.in);

    public void run() {
        StringBuilder str = new StringBuilder(read.next());
        if(str.length() < 26){
            System.out.println(-1);
            return;
        }

        ArrayList< ArrayList<Integer> >arr = new ArrayList< ArrayList<Integer> >();

        for(int i=0;i<26;i++){
            ArrayList<Integer> temp = new ArrayList<Integer>();
            arr.add(temp);
        }

        for(int i=0;i<str.length();i++){
            arr.get(str.charAt(i)-'a').add(i);
        }

        int min = -1;
        int count =0;
        boolean istrue = true;
        TreeMap<Integer,Integer> myMap = new TreeMap<Integer,Integer>();
        for(int i=0;i<26;i++){
            for(int j=0;j<arr.get(i).size();j++){
                if(min < arr.get(i).get(j)){
                    myMap.put(arr.get(i).get(j), arr.get(i).get(j));
                }
            }
            if(myMap.isEmpty() ==  true){
                istrue = false;
            }else{
                int temp = myMap.firstKey();
                min = temp;
                myMap.remove(temp);
                str.setCharAt(temp, (char)(count +'a'));
                count++;
                if(count >= 26) break; 
            }
        }

        if(istrue) System.out.println(str);
        else System.out.println(-1);
    }



    public long modAdd(long a, long b) { return (a % mod + b % mod) % mod;}

    public long modSub(long a, long b) { return ((a % mod - b % mod) % mod);}

    public long modMul(long a, long b) { return ((a % mod) * (b % mod)) % mod;}

    public long modDiv(long a, long b) { return ((a % mod) * (binaryExp(b, mod - 2))) % mod;}

    public long modPow(long a) { return a % (mod - 1);}

    public long binaryExp(long a, long pow) {
        a = a % mod;
        if (pow == 0) {
            return 1;
        } else if (pow == 1) {
            return a;
        } else {
            long half = pow / 2;
            long temp = binaryExp(a, half);
            if (pow % 2 == 0) {
                return (temp * temp) % mod;
            } else {
                return ((a % mod) * ((temp * temp) % mod)) % mod;
            }
        }
    }

    public static void main(String args[]) throws Exception {
        new Thread(null, new c(), "Main", 1 << 27).start();
    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        public int nextInt() {
            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));

            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }

        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));

            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return readString();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

}