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 codeforces3
{    
    public static void main(String args[])
    {
        PrintWriter out=new PrintWriter(System.out);
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        String s=sc.next();
        int arr[]=new int[26];
        for(int i = 0 ;i<s.length();i++)
        {
            arr[s.charAt(i)-97]=1;
        }
        if(n<k)
        {
            out.print(s);
            for(int i = 0 ;i<26;i++)
            {
                if(arr[i]==1)
                {
                    for(int j =0;j<k-n;j++)
                    {
                        out.print((char)(i+97));
                    }
                    out.close();
                    System.exit(0);
                }
            }
        }
        else
        {
            StringBuilder ans = new StringBuilder("");
            int minchar=0;
            for(int i = 0 ;i<26;i++)
            {
                if(arr[i]==1)
                {
                    minchar=i;
                    break;
                }
            }
            for(int i = 0 ;i<k;i++)
            {
                ans.append(s.charAt(i));
            }
            for(int i = k-1;i>=0;i--)
            {
                int pos=s.charAt(i)-97;
                for(int j=pos+1;j<26;j++)
                {
                    if(arr[j]==1)
                    {
                        out.print(ans.substring(0,i)+(char)(j+97));
                        for(int k1 =i+1;k1<k;k1++)
                        {
                            out.print((char)(minchar+97));
                        }
                        out.close();
                        System.exit(0);
                    }
                }
            }
        }
    }
}