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.util.*;

public class CFC {

    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;
    final long MOD = 1000L * 1000L * 1000L + 7;
    int[] dx = {0, -1, 0, 1};
    int[] dy = {1, 0, -1, 0};
    private static final String yes = "YES";
    private static final String no = "NO";
    
    void solve() throws IOException {
        int n = nextInt();
        int k = nextInt();
        String str = nextString();
        int m = 26;
        boolean[] vis = new boolean[m];
        for (int i = 0; i < str.length(); i++) {
            vis[str.charAt(i) - 'a'] = true;
        }

        int[] next = new int[m];
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            int tmp = Integer.MAX_VALUE;
            for (int j = i + 1; j < m; j++) {
                if (vis[j]) {
                    tmp = j;
                    break;
                }
            }
            next[i] = tmp;
            if (vis[i]) {
                min = Math.min(min, i);
            }
        }

        if (k > n) {
            StringBuilder sb = new StringBuilder(str);
            for (int i = 0; i < k - n; i++) {
                sb.append((char) (min + 'a'));
            }
            out(sb.toString());
            return;
        }

        char[] arr = str.toCharArray();

        int i = k - 1;
        while (i >= 0) {
            char cur = str.charAt(i);
            int nxt = next[cur - 'a'];
            if (nxt != Integer.MAX_VALUE) {
                arr[i] = (char) (nxt + 'a');
                break;
            }
            i--;
        }
        for (int j = i + 1; j < k; j++) {
            arr[j] = (char) (min + 'a');
        }

        StringBuilder sb = new StringBuilder("");
        for (i = 0; i < k; i++) {
            sb.append(arr[i]);
        }
        outln(sb.toString());
    }

    void shuffle(int[] a) {
        int n = a.length;
        for(int i = 0; i < n; i++) {
            int r = i + (int) (Math.random() * (n - i));
            int tmp = a[i];
            a[i] = a[r];
            a[r] = tmp;
        }
    }

    int gcd(int a, int b) {
        while(a != 0 && b != 0) {
            int c = b;
            b = a % b;
            a = c;
        }
        return a + b;
    }
    private void outln(Object o) {
        out.println(o);
    }
    private void out(Object o) {
        out.print(o);
    }
    public CFC() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }
    public static void main(String[] args) throws IOException {
        new CFC();
    }

    public long[] nextLongArr(int n) throws IOException{
        long[] res = new long[n];
        for(int i = 0; i < n; i++)
            res[i] = nextLong();
        return res;
    }
    public int[] nextIntArr(int n) throws IOException {
        int[] res = new int[n];
        for(int i = 0; i < n; i++)
            res[i] = nextInt();
        return res;
    }
    public String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }
    public String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }
    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}
