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.io.IOException;
import java.io.InputStream;
import java.util.*;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.pow;
import static java.lang.Math.abs;

import static java.lang.String.format;


public class Main {
    final static int INF = Integer.MAX_VALUE >> 1;
    final static int MOD = 1000000007;
    final static int[] dx4 = {0, -1, 1, 0};
    final static int[] dy4 = {-1, 0, 0, 1};
    final static int[] dx8 = {-1, -1, -1, 0, 0, 1, 1, 1};
    final static int[] dy8 = {-1, 0, 1, -1, 1, -1, 0, 1};

    public static void main(String[] args) {
        Scanner sc = new Scanner();
        String s = sc.next();
        int[] counter = new int[26];
        for (char c : s.toCharArray()) {
            counter[c - 'a']++;
        }
        putE(Arrays.toString(counter));
        for (int i = 0; i < 26; i++) {
            if (counter[i] == 0) {
                put(s + (char) (i + 'a'));
                return;
            }
        }
        int[] c = new int[s.length()];
        for(int i=0;i<c.length;i++){
            c[i]=s.charAt(i)-'a';
        }
        if(!Permutation.nextPermutation(c)){
            put(-1);
            return;
        }
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<c.length;i++){
            sb.append((char)(c[i]+'a'));
            if(c[i]!=s.charAt(i)-'a')break;
        }
        put(sb);
    }

    public static class Permutation {
        public static boolean nextPermutation(int[] p) {
            for (int i = p.length - 2; i >= 0; i--) {
                if (p[i] >= p[i + 1]) continue;
                for (int j = p.length - 1; ; j--) {
                    if (p[j] <= p[i]) continue;
                    int t = p[i];
                    p[i] = p[j];
                    p[j] = t;
                    for (int l=i+1,k = p.length - 1; l < k; ++l, --k) {
                        t = p[l];
                        p[l] = p[k];
                        p[k] = t;
                    }
                    return true;
                }
            }
            return false;
        }
    }


    public static int upper_bound(long[] a, long val) {
        return upper_bound(a, 0, a.length, val);
    }

    public static int upper_bound(long[] a, int l, int r, long val) {
        if (r - l == 1) {
            if (a[l] > val) return l;
            return r;
        }
        int mid = (l + r) / 2;
        if (a[mid] > val) {
            return upper_bound(a, l, mid, val);
        } else {
            return upper_bound(a, mid, r, val);
        }
    }

    public static <T> int upper_bound(T[] a, int l, int r, T val, Comparator<T> comparator) {
        if (r - l == 1) {
            if (comparator.compare(a[l], val) > 0) return l;
            return r;
        }
        int mid = (l + r) / 2;
        if (comparator.compare(a[mid], val) > 0) {
            return upper_bound(a, l, mid, val, comparator);
        } else {
            return upper_bound(a, mid, r, val, comparator);
        }
    }

    public static int lower_bound(long[] a, long val) {
        return lower_bound(a, 0, a.length, val);
    }

    public static int lower_bound(long[] a, int l, int r, long val) {
        if (r - l == 1) {
            if (a[l] < val) return r;
            return l;
        }
        int mid = (l + r) / 2;
        if (a[mid] < val) {
            return lower_bound(a, mid, r, val);
        } else {
            return lower_bound(a, l, mid, val);
        }

    }

    public static <T> int lower_bound(T[] a, int l, int r, T val, Comparator<T> comparator) {
        if (r - l == 1) {
            if (comparator.compare(a[l], val) < 0) return r;
            return l;
        }
        int mid = (l + r) / 2;
        if (comparator.compare(a[mid], val) < 0) {
            return lower_bound(a, mid, r, val, comparator);
        } else {
            return lower_bound(a, l, mid, val, comparator);
        }
    }


    public static void print(Object object) {
        System.out.print(object);
    }

    public static void put(Object object) {
        System.out.println(object);
    }

    public static void put() {
        System.out.println();
    }

    public static void printE(Object object) {
        System.err.print("DEBUG:" + object);
    }

    public static void putE(Object object) {
        System.err.println("DEBUG:" + object);
    }

    public static void putE() {
        System.err.println("DEBUG:");
    }

    final static private class Scanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;

        private boolean hasNextByte() {
            if (ptr < buflen) {
                return true;
            } else {
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (buflen <= 0) {
                    return false;
                }
            }
            return true;
        }

        private int readByte() {
            if (hasNextByte())
                return buffer[ptr++];
            else
                return -1;
        }

        private boolean isPrintableChar(int c) {
            return 33 <= c && c <= 126;
        }

        public boolean hasNext() {
            while (hasNextByte() && !isPrintableChar(buffer[ptr]))
                ptr++;
            return hasNextByte();
        }

        public String next() {
            if (!hasNext())
                throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while (isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public long nextLong() {
            if (!hasNext())
                throw new NoSuchElementException();
            long n = 0;
            boolean minus = false;
            int b = readByte();
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            if (b < '0' || '9' < b) {
                throw new NumberFormatException();
            }
            while (true) {
                if ('0' <= b && b <= '9') {
                    n *= 10;
                    n += b - '0';
                } else if (b == -1 || !isPrintableChar(b)) {
                    return minus ? -n : n;
                } else {
                    throw new NumberFormatException();
                }
                b = readByte();
            }
        }

        public int nextInt() {
            long nl = nextLong();
            if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
                throw new NumberFormatException();
            return (int) nl;
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    final static private class FixedLongPair {
        final public long x, y;
        final static public FixedLongPair ZEROS = new FixedLongPair(0, 0);

        FixedLongPair(long x, long y) {
            this.x = x;
            this.y = y;
        }

        public static double distance(FixedLongPair flp1, FixedLongPair flp2) {
            double x = (double) flp1.x - flp2.x;
            double y = (double) flp1.y - flp2.y;
            return Math.sqrt(x * x + y * y);
        }

        @Override
        public int hashCode() {
            return (int) x + (int) y;
        }

        @Override
        public boolean equals(Object obj) {
            boolean result = super.equals(obj);
            if (obj.getClass() != this.getClass()) {
                return false;
            }
            FixedLongPair pair = (FixedLongPair) obj;
            if (this.x == pair.x && this.y == pair.y) return true;
            return false;
        }

        @Override
        public String toString() {
            return String.format(FixedLongPair.class.getSimpleName() + ":(%d,%d)", x, y);
        }
    }

    final static private class FixedIntPair {
        final public int x, y;
        final static public FixedIntPair ZEROS = new FixedIntPair(0, 0);

        FixedIntPair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        public static double distance(FixedIntPair fip1, FixedIntPair fip2) {
            double x = (double) fip1.x - fip2.x;
            double y = (double) fip1.y - fip2.y;
            return Math.sqrt(x * x + y * y);
        }

        @Override
        public int hashCode() {
            return x + y;
        }

        @Override
        public boolean equals(Object obj) {
            boolean result = super.equals(obj);
            if (obj.getClass() != this.getClass()) {
                return false;
            }
            FixedIntPair pair = (FixedIntPair) obj;
            if (this.x == pair.x && this.y == pair.y) return true;
            return false;
        }

        @Override
        public String toString() {
            return String.format(FixedIntPair.class.getSimpleName() + ":(%d,%d)", x, y);
        }
    }

    final static private class Tuple<T, V> {
        //immutabl1でないことに注意(T,Vがmutableの場合変更可能)
        final private T t;
        final private V v;

        Tuple(T t, V v) {
            this.t = t;
            this.v = v;
        }

        public T getT() {
            return t;
        }

        public V getV() {
            return v;
        }

        @Override
        public int hashCode() {
            return (t.hashCode() + v.hashCode());
        }

        @Override
        @SuppressWarnings("unchecked")
        public boolean equals(Object obj) {
            if (obj.getClass() != this.getClass()) {
                return false;
            }
            Tuple<T, V> tuple = (Tuple<T, V>) obj;
            return tuple.t.equals(this.t) && tuple.v.equals(this.v);
        }

        @Override
        public String toString() {
            return String.format("<Tuple>=<%s,%s>", t, v);
        }
    }

    final static private class Util {
        static long gcd(long a, long b) {
            //最大公約数　
            if (a % b == 0) return b;
            return gcd(b, a % b);
        }

        static long lcm(long a, long b) {
            //最小公倍数
            long gcd = gcd(a, b);
            long result = b / gcd;
            return a * result;
        }

        static <T extends Comparable<T>> Map<T, Integer> count(List<T> list) {
            //副作用
            Collections.sort(list);
            Map<T, Integer> result = new HashMap<>();
            int l = 0, r = 0;
            while (l < list.size()) {
                while (r < list.size() - 1 && list.get(r).equals(r + 1)) {
                    r++;
                }
                result.put(list.get(r), r - l + 1);
                r++;
                l = r;
            }
            return result;

        }

        static Map<Integer, Integer> count(int[] array) {
            //副作用
            Arrays.sort(array);
            Map<Integer, Integer> result = new HashMap<>();
            int l = 0, r = 0;
            while (l < array.length) {
                while (r < array.length - 1 && array[r] == array[r + 1]) {
                    r++;
                }
                result.put(array[l], r - l + 1);
                r++;
                l = r;
            }
            return result;
        }

        static <T> String toStringBWS(Iterable<T> iterable) {
            Iterator<T> ite = iterable.iterator();
            return toStringBWS(ite);
        }

        static <T> String toStringBWS(Iterator<T> ite) {
            StringBuilder sb = new StringBuilder();
            sb.append(ite.next());
            while (ite.hasNext()) {
                sb.append(" ");
                sb.append(ite.next());
            }
            return sb.toString();
        }

        static int[] factoringInPrimeNumbers(long n, int size) {
            //素因数分解
            //sizeがnに比べて小さい場合完全に素因数分解出来ていない可能性がある
            int[] result = new int[size];
            for (int i = 2; n > 1 && i < result.length; i++) {
                while (n % i == 0) {
                    result[i]++;
                    n /= i;
                }
            }
            return result;

        }

        public static long min(long... longs) {
            if (longs.length == 0) throw new IllegalArgumentException("Argument.length==0");
            long min = Long.MAX_VALUE;
            for (int i = 0; i < longs.length; i++) {
                min = Math.min(min, longs[i]);
            }
            return min;
        }

        public static long max(long... longs) {
            if (longs.length == 0) throw new IllegalArgumentException("Argument.length==0");
            long max = Long.MIN_VALUE;
            for (int i = 0; i < longs.length; i++) {
                max = Math.max(max, longs[i]);
            }
            return max;
        }
    }
}
