And where the are the phone numbers?

You are given a string s consisting of lowercase English letters and an integer k. Find the lexicographically smallest string t of length k, such that its set of letters is a subset of the set of letters of s and s is lexicographically smaller than t.

It's guaranteed that the answer exists.

Note that the set of letters is a set, not a multiset. For example, the set of letters of abadaba is {a, b, d}.

String p is lexicographically smaller than string q, if p is a prefix of q, is not equal to q or there exists i, such that pi < qi and for all j < i it is satisfied that pj = qj. For example, abc is lexicographically smaller than abcd , abd is lexicographically smaller than abec, afa is not lexicographically smaller than ab and a is not lexicographically smaller than a.

Input

The first line of input contains two space separated integers n and k (1 ≤ n, k ≤ 100 000) — the length of s and the required length of t.

The second line of input contains the string s consisting of n lowercase English letters.

Output

Output the string t conforming to the requirements above.

It's guaranteed that the answer exists.

Examples

Input

3 3
abc


Output

aca


Input

3 2
abc


Output

ac


Input

3 3
ayy


Output

yaa


Input

2 3
ba


Output

baa

Note

In the first example the list of strings t of length 3, such that the set of letters of t is a subset of letters of s is as follows: aaa, aab, aac, aba, abb, abc, aca, acb, .... Among them, those are lexicographically greater than abc: aca, acb, .... Out of those the lexicographically smallest is aca.
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
import java.util.stream.Collectors;
import java.util.stream.Stream.*;


public class CodeForces {

    static FastScanner sc = new FastScanner();

    static int pvalue = (int) Math.pow(10, 9);
    static int svalue = (int) Math.pow(10, 18);

    public static void main(String[] args) {

        int n = sc.nextInt();
        int k = sc.nextInt();
        char[] str = sc.nextLine().toCharArray();
        char[] ans = new char[k];
        int max = str[0];
        int min = str[0];
        for (int i = 0; i < str.length; i++) {
            max = Math.max(str[i], max);
            min = Math.min(str[i], min);

        }
        if (k <= n) {
            int l = str.length;
            for (int i = k - 1; i >= 0; i--) {
                if (str[i] != max) {
                    l = i;
                    break;
                }
            }
            int minOverl = max;
            for (int i = 0; i < str.length; i++) {
                if (str[i] > str[l]) {
                    minOverl = Math.min(str[i], minOverl);
                }
            }
            for (int i = 0; i < l; i++) {
                ans[i] = str[i];
            }
            ans[l] = (char) minOverl;
            for (int i = l + 1; i < k; i++) {
                ans[i] = (char) min;
            }
        } else {// k>n
            for (int i = 0; i < n; i++) {
                ans[i] = str[i];
            }
            for (int i = n; i < k; i++) {
                ans[i] = (char) min;
            }
        }
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < ans.length; i++) {
            out.append(ans[i]);
        }
        log(out);
    }

    private static void logintarrayllist(List<Integer> currList){
        for (Integer a: currList) {
            System.out.print(a + " ");
        }
        System.out.println();
    }

    private static void logintarray(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    private static void logchararray(char[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }


    private static void loglongarray(long[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    private static void log(Object... args) {
        System.out.println(args[0]);
        // ...
    }


    static class FastScanner {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
        public FastScanner() {
            reader = new BufferedReader(new InputStreamReader(System.in), 32768);
            tokenizer = null;
        }
        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 int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public double nextDouble() {
            return Double.parseDouble(next());
        }
        public String nextLine() {
            try {
                return reader.readLine();
            } catch(IOException e) {
                throw new RuntimeException(e);
            }
        }
    }


}
