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

public class PhoneNumbers {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static boolean[] mrk;

    public static void main(String args[]) throws IOException {
        FastReader s = new FastReader();
        int n = s.nextInt();
        int k = s.nextInt();
        String str = s.next();
        mrk = new boolean[30];
        Arrays.fill(mrk, false);
//        HashMap<Character,Integer> hm = new HashMap<>();
        char lowest = '{';
        char highest = '`';
        for(int i=0;i<str.length();i++){
            char c = str.charAt(i);
            mrk[c - 'a'] = true;
//            hm.put(c,1);
            if(c<lowest){
                lowest = c;
            }
            if(c>highest){
                highest = c;
            }
        }


        StringBuilder ans = new StringBuilder();

        if(k>n){
            char[] repeat = new char[k-n];
            Arrays.fill(repeat,lowest);
            ans = new StringBuilder(new String(repeat));
//            ans = str+ans;
            ans.insert(0,str);
            System.out.println(ans);
            return;
        }

        for(int i=k-1;i>=0;i--){
            char c = str.charAt(i);

            if(c==highest){
//                ans = lowest+ ans;
                ans.insert(0,lowest);
            }else{
//                char check = c;
//                check++;
//                while(check!='{'){
//                    if(hm.containsKey(check)){
//                        break;
//                    }
//                    check++;
//                }
                int y = findGreater(c - 'a');
                ans.insert(0,(char)(y+ 'a'));
                ans.insert(0,str.substring(0,i));
//                ans = ((char)(y+ 'a')) + ans;
//                ans = str.substring(0,i)+ans;
                break;
            }
        }
        System.out.println(ans);





//        HashMap<Character,Integer> hm = new HashMap<>();
//        char lowest = '{';
//        for(int i=0;i<str.length();i++){
//            if(hm.containsKey(str.charAt(i))){
//                hm.put(str.charAt(i),hm.get(str.charAt(i))+1);
//            }else{
//                hm.put(str.charAt(i),1);
//            }
//            if(str.charAt(i)<lowest){
//                lowest = str.charAt(i);
//            }
//        }
//        String ans = "";
//        if(k>n){
//            char[] repeat = new char[k-n];
//            Arrays.fill(repeat,lowest);
//            ans = new String(repeat);
//            ans = str+ans;
//            System.out.println(ans);
//            return;
//        }
//        for(int i=k-1;i>=0;i--){
//            char c = str.charAt(i);
//            int flag = 0;
//            c++;
//            while(c!='{'){
//                if(hm.containsKey(c)){
//                    flag = 1;
//                    break;
//                }
//                c++;
//            }
//            if(flag==1){
//                ans = c + ans;
//                ans = str.substring(0,i)+ans;
//                break;
//            }else{
//                ans = lowest+ ans;
//            }
//
//        }
//        System.out.println(ans);


    }


    private static int findGreater(int k) {
        for (int i = 0; i < 30; i++) {
            if (i > k && mrk[i]) return i;
        }
        return -1;
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}
