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.
/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        // your code goes here
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        int k=scan.nextInt();
        String s=scan.next();
        TreeSet<Integer> ts=new TreeSet<Integer>();
        for(int i=0;i<n;i++){
            ts.add(s.charAt(i)-'a');
        }
        //System.out.println(ts);
        if(k>n){
            char c=(char)(ts.first()+'a');
            System.out.print(s);
            for(int i=n+1;i<=k;i++){
                System.out.print(c);
            }
            return;
        }
        char[] c=new char[k];
        int done=0;
        for(int i=k-1;i>=0;i--){
            
            if(done==1){
                c[i]=s.charAt(i);
                continue;
            }
            if(s.charAt(i)-'a'<ts.last()){
                //int done=0;
                while(true){
                    //System.out.println(ts);
                        if(ts.first()==s.charAt(i)-'a'){ 
                            //System.out.println(s.charAt(i)-'a');
                            ts.remove(ts.first());
                            break;
                        }
                        
                        ts.remove(ts.first());
                }
                c[i]=(char)(ts.first()+'a');
                done=1;
            }
            else if(s.charAt(i)-'a'==ts.last()){
                //System.out.println(s.charAt(i));
                c[i]=(char)(ts.first()+'a');
            }
        }
        
        for(int i=0;i<k;i++){
            System.out.print(c[i]);
        }
    }
}