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


public class Main {

    public static String Y = "Yes";
    public static String N = "No";
    public static long MOD = (long) (Math.pow(10, 9) + 7);
    public static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {

        String s = n();
        char clist[] = s.toCharArray();
        int n = s.length();

        if ("zyxwvutsrqponmlkjihgfedcba".equals(s)) {
            out(-1);
            return;
        }

        boolean[] isExist = new boolean['z' + 1];
        for (int i = 0; i < 'z' + 1; i++) {
            isExist[i] = false;
        }
        for (char c : clist) {
            isExist[c] = true;

        }

        String ans = "";

        if (n != 26) {
            ans = s;
            for (int i = 'a'; i < 'z' + 1; i++) {
                if (!isExist[i]) {
                    ans += (char) i;
                    break;
                }
            }
        } else {
            int i = 26;
            char tmp = 'a' - 1;
            for (int j = 25; j >= 0; j--) {
                if (clist[j] > tmp) {
                    i--;
                } else {
                    break;
                }
                tmp = clist[j];
            }
            char max = 'z' + 1;
            char min = clist[i - 1];
            for (int j = i; j < 26; j++) {
                if (clist[j] > min) {
                    if (max > clist[j]) {
                        max = clist[j];
                    }
                }
            }

            ans = "";
            for (int j = 0; j <= i - 2; j++) {
                ans += clist[j];
            }
            ans += max;
        }

        out(ans);

    }

    /*
     * 以下メソッド集
     */
    static double[] sort(double[] r) {

        Arrays.sort(r);
        return r;
    }

    static int[] sort(int[] r) {

        Arrays.sort(r);
        return r;
    }

    static void debug() {

        out("---");
    }

    static void debug(long a) {

        out("-------");
        out(a);
        out("-------");
    }

    static void debug(String a) {

        out("-------");
        out(a);
        out("-------");
    }

    static long[] sort(long[] n) {

        Arrays.sort(n);
        return n;
    }

    static int ketasuu(int n) {

        String str = "" + n;
        return str.length();
    }

    static int account(String str) {

        String target = "AC";
        int count = 0;
        int len = str.length();
        for (int i = 0; i < len - 1; i++) {
            if (target.equals(str.substring(i, i + target.length()))) {
                count++;
            }
        }
        return count;
    }

    static int ni() {

        return sc.nextInt();
    }

    static long nl() {

        return sc.nextLong();
    }

    static double nd() {

        return sc.nextDouble();
    }

    static String n() {

        return sc.next();
    }

    static char[] nc() {

        return sc.next().toCharArray();
    }

    static int kaijo(int n) {

        if (n == 0 || n == 1) {
            return 1;
        } else {
            return n * kaijo(n - 1);
        }
    }

    static int fib(int n) {

        return (n == 1 || n == 0) ? n : fib(n - 2) + fib(n - 1);
    }

    static long lcm(long m, long n) {

        return m * n / gcd(m, n);
    }

    static int lcm(int m, int n) {

        return m * n / gcd(m, n);
    }

    static long gcd(long a, long b) {

        return (b == 0) ? a : gcd(b, a % b);
    }

    static int gcd(int a, int b) {

        return (b == 0) ? a : gcd(b, a % b);
    }

    static void out(String info) {

        System.out.println(info);
    }

    static void out(int info) {

        System.out.println(info);
    }

    static void out(double info) {

        System.out.println(info);
    }

    static void out(long info) {

        System.out.println(info);
    }

    static void out(char info) {

        System.out.println(info);
    }

    static void out(Object obj) {

        System.out.println(obj.toString());
    }

    static void outn(String info) {

        System.out.print(info);
    }

    static void outn(int info) {

        System.out.print(info);
    }

    static void outn(double info) {

        System.out.print(info);
    }

    static void outn(long info) {

        System.out.print(info);
    }

    static void outn(char info) {

        System.out.print(info);
    }

    static double max(double d, double e) {

        return Math.max(d, e);
    }

    static long max(long a, long b) {

        return Math.max(a, b);
    }

    static long min(long d, long e) {

        return Math.min(d, e);
    }

    static int min(int a, int b) {

        return Math.min(a, b);
    }
}


class XY {

    int h;
    int c;

    XY(int h, int c) {
        this.h = h;
        this.c = c;
    }
}
