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.
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
//package C;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

/**
 *
 * @author Hemant Dhanuka
 */
public class C {
     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;
        }
    }
    public static void main(String[] args) {
        FastReader s=new FastReader();
         //Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int k=s.nextInt();
        String given=s.next();
        
        boolean arr[]=new boolean[26];
        for(int i=0;i<given.length();i++){
            arr[given.charAt(i)-97]=true;
        }
        
       char smallest='a';
       for(int i=0;i<26;i++){
           if(arr[i]){
               smallest=(char)(i+97);
               break;
           }
       }
       String Output="";
       char charOutput[]=new char[k];
        if(k>n){
            for(int i=0;i<n;i++){
                charOutput[i]=given.charAt(i);
            }
            //Output=given;
            for(int i=n;i<k;i++){
                charOutput[i]=smallest;
            }
        }
        else{
            //if k choti ya equal h n ke
            char found='a';
            int i=k-1;
            outer :for(;i>=0;i--){
                char c=given.charAt(i);
                int startingLoop=(c-97)+1;
                
                for(;startingLoop<26;startingLoop++){
                    if(arr[startingLoop]){
                        found=(char)(startingLoop+97);
                        break outer;
                    }
                    
                }
                
            }
            
            for(int j=0;j<i;j++){
                charOutput[j]=given.charAt(j);
            }
            charOutput[i]=found;
            
            for(int j=i+1;j<k;j++){
                charOutput[j]=smallest;
            }            
            
        }
        
             for(char c:charOutput){
                 System.out.print(c);
             }        
    }
}
