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.*;
import java.text.*;
public class TC{
    static final long MOD = (long)1e9+7;
    static int MAX = (int)1e6+1;
    static double eps = 1e-9;
    static FastReader in;

    static int N, K;
    static boolean found;
    static TreeSet<Character> set;
    static String ans = "", s;
    static StringBuilder cur = new StringBuilder("");
    public static void main(String[] args) throws Exception{
        in = new FastReader();
        N = ni();K = ni();s = n();
        set = new TreeSet<>();
        for(int i = 0; i< s.length(); i++)set.add(s.charAt(i));
        for(int i = 0; i< K; i++)cur.append(" ");
        solve(0,true);
    }
    
    static void solve(int idx, boolean flag){
        if(found)return;
        if(idx==K){
            if(flag)return;
            found = true;
            pn(cur.toString());
        }else{
            if(flag && idx<s.length()){
                cur.setCharAt(idx,s.charAt(idx));
                solve(idx+1, flag);
                if(found)return;
                Character c = set.ceiling((char)(s.charAt(idx)+1));
                if(c==null)return;
                cur.setCharAt(idx, c);
                solve(idx+1,false);
            }else{
                cur.setCharAt(idx,(char)(set.first()));
                solve(idx+1,false);
            }
        }
    }
    
    static boolean valid(int x){
        return x>=0 && x<64;
    }
    
    static boolean adjacent(int x1, int y1, int x2, int y2){
        return (Math.max(Math.abs(x1-x2), Math.abs(y1-y2))<2);
    }
    
    static long mod(long m){
        return (m%MOD+MOD)%MOD;
    }
    
    static void p(Object o){
        System.out.print(o);
    }
    
    static void pn(Object o){
        System.out.println(o);
    }
    
    static String n(){
        return in.next();
    }
    
    static String nln(){
        return in.nextLine();
    }
    
    static int ni(){
        return Integer.parseInt(in.next());
    }
    
    static long nl(){
            return Long.parseLong(in.next());
    }
    
    static double nd(){
        return Double.parseDouble(in.next());
    }
    
    static class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }
 
        String next(){
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        String nextLine(){
            String str = "";
            try{
                str = br.readLine();
            }catch (IOException e){
                e.printStackTrace();
            }
            return str;
        }
    }
} 