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

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        String s = in.next();
        char[] c = s.toCharArray();
        Arrays.sort(c);
        if (k > n) {
            StringBuilder result = new StringBuilder(k);
            result.append(s);
            for (int i = n; i < k; i++) {
                result.append(c[0]);
            }
            System.out.println(result.toString());
            return;
        }

        char[] result = new char[k];
        for (int i = k - 1; i >= 0; i--) {
            char curC = s.charAt(i);
            Character minBigger = findMinBigger(c, curC);
            if (minBigger != null) {
                result[i] = minBigger;
                for (int j = i - 1; j >= 0; j--) {
                    result[j] = s.charAt(j);
                }
                System.out.println(new String(result));
                return;
            } else {
                result[i] = c[0];
            }
        }
        System.out.println(new String(result));
    }

    private static Character findMinBigger(char[] c, char curC) {
        if (c.length < 3) {
            for (char aC : c) {
                if (aC > curC) {
                    return aC;
                }
            }
            return null;
        }

        int low = 0;
        int high = c.length - 1;
        int mid;
        while (low <= high) {
            mid = (low + high) / 2;
            char midValue = c[mid];
            if (midValue > curC) {
                if (c[mid - 1] > curC) {
                    high = mid - 1;
                } else {
                    return midValue;
                }
            } else {
                low = mid + 1;
            }
        }
        return null;
    }
}
