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.*;
import java.io.*;

public class CF {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        pw.println(solve(br.readLine(), n, k));

        pw.close();
    }

    private static String solve(String s, int n, int k) {
        if (n < k) {
            char end = minChar(s);
            StringBuilder ret = new StringBuilder(s);
            for (int i = 0; i < k - n; i++) {
                ret.append(end);
            }

            return ret.toString();
        }

        char max = maxChar(s);
        char min = minChar(s);
        int i = k - 1;
        for (; i >= 0; i--) {
            if (s.charAt(i) != max) break;
        }

        int minDiff = Integer.MAX_VALUE;
        for (int j = 0; j < s.length(); j++) {
            if (s.charAt(j) > s.charAt(i)) {
                minDiff = Math.min(minDiff, s.charAt(j) - s.charAt(i));
            }
        }

        StringBuilder ret = new StringBuilder(s.substring(0, i) + (char)(s.charAt(i) + minDiff));
        while (ret.length() < k) {
            ret.append(min);
        }

        return ret.toString();
    }

    private static char maxChar(String s) {
        char max = 'a';
        for (int i = 0; i < s.length(); i++) {
            max = (char) Math.max(max, s.charAt(i));
        }
        return max;
    }

    private static char minChar(String s) {
        char min = 'z';
        for (int i = 0; i < s.length(); i++) {
            min = (char) Math.min(min, s.charAt(i));
        }
        return min;
    }
}

/*
If runtime error, check for division by 0
In USACO, make sure spaces are right
Substring 2nd parameter is the LENGTH of the String
Remember that in for (int i = 0; i < k; i++) to not update k in body
 */