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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class Exercise3 extends Thread {

    static BufferedReader in;
    static PrintWriter out;
    static StringTokenizer st;

    private void solve() throws IOException {
        int lenght = nextInt();
        int setLen = nextInt();
        String s = nextToken();

        String finalString = null;

        NavigableSet<Character> set = new TreeSet<>();

        for (int i = 0; i < s.length(); i++) {
            set.add(s.charAt(i));
        }

        Character lowest = set.first();
        Character highest = set.last();

        if (setLen > s.length()) {
            int add = setLen - s.length();
            StringBuilder builder = new StringBuilder(s);
            for (int i = 0; i < add; i++) {
                builder.append(lowest);
            }
            finalString = builder.toString();
        } else {
            for (int i = setLen - 1; i >= 0; i--) {
                if (!highest.equals(s.charAt(i))) {
                    Character c = s.charAt(i);
                    Character higher = set.higher(c);
                    StringBuilder b = new StringBuilder();
                    b.append(s.substring(0, i));
                    b.append(higher);
                    int add = setLen - i - 1;
                    if (add > 0) {
                        for (int j = 0; j < add; j++) {
                            b.append(lowest);
                        }
                    }

                    finalString = b.toString();
                    break;
                }
            }
        }

        System.out.println(finalString);
    }

    public static void main(String[] args) {
        new Exercise3().run();
    }

    @Override
    public void run() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);

            solve();

            out.close();
        } catch (IOException e) {
            e.printStackTrace(System.err);
            System.exit(1);
        }
    }

    private String nextToken() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            String line = in.readLine();

            if (line == null) {
                return null;
            }

            st = new StringTokenizer(line);
        }

        return st.nextToken();
    }

    private int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    private long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    private double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}
