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 C_Phone_Numbers{
    static int MOD = (int)1e9+7;
    
    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws Exception{
        int[] nk = in.readA();
        int n = nk[0], k = nk[1], distinct = 0;
        char[] str = in.readLine().toCharArray();
        boolean alpha[] = new boolean[26];
        for(int i = 0; i < n; i++){
            if(!alpha[str[i]-'a'])
                distinct++;
            alpha[str[i]-'a'] = true;
        }
        char[] set = new char[distinct];
        for(int i = 0, idx = 0; i < 26; i++){
            if(alpha[i]){
                set[idx++] = (char)('a'+i);
            }
        }
        Arrays.sort(set);
        char[] ans = new char[k];
        boolean gtr = false;
        while(k>n){
            gtr = true;
            ans[k-1] = set[0];
            k--;
        }
        for(int i = k-1; i >= 0; i--){
            int idx = Arrays.binarySearch(set,str[i]);
            if(!gtr){
                idx = (idx + 1)%set.length;
            }
            ans[i] = set[idx];
            gtr = gtr || ans[i]>str[i];
        }
        System.out.println(new String(ans));
    }

    static Inputer in;
    static {
        in = new Inputer();
    }

    static class Inputer{
        BufferedReader br;
        Inputer(){
            try{
                br = new BufferedReader(new InputStreamReader(System.in));
            }
            catch(Exception e){}
        }
        public int readInt() throws Exception{
            return Integer.parseInt(readLine());
        }
        public long readLong() throws Exception{
            return Long.parseLong(readLine());
        }
        public int[] readA(String delim) throws Exception{
            String[] s = readLine().split(delim);
            int[] A = new int[s.length];
            for(int i = 0; i < s.length; i++)
                A[i] = Integer.parseInt(s[i]);
            return A;
        }
        public int[] readA() throws Exception{
            String[] s = readLine().split("\\s+");
            int[] A = new int[s.length];
            for(int i = 0; i < s.length; i++)
                A[i] = Integer.parseInt(s[i]);
            return A;
        }
        public long[] readLA() throws Exception{
            String[] s = readLine().split("\\s+");
            long[] A = new long[s.length];
            for(int i = 0; i < s.length; i++)
                A[i] = Long.parseLong(s[i]);
            return A;
        }
        public String readLine() throws Exception{
            return br.readLine();
        }
        public int[] copyA(int[] A){
            int[] B = new int[A.length];
            for(int i= 0 ; i < A.length; i++)
                B[i] = A[i];
            return B;
        }
    }
    static void shuffle(int[] A){
        int n = A.length;
        Random rand = new Random();
        for(int t = 0; t < A.length; t++){
            int i1 = rand.nextInt(n);
            int i2 = rand.nextInt(n);
            int tmp = A[i1];
            A[i1] = A[i2];
            A[i2] = tmp;
        }
    }
    static class Pair{
        int first, second;
        Pair(){
        }
        Pair(int a, int b){
            first = a;
            second = b;
        }
        @Override
        public String toString() {
            return "{"+first+","+second+"}";
        }
    }
}