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 Solution {
	
		   public static long log2(long x)
			{
				long p=1;
				long ans=0;
				while(x>=p)
				{
					p*=2;
					ans++;
				}
				return ans-1;
			}
		   
		   
		   public static void extendedgcd(int a, int b)
		   {
			   x=0;
			   y=0;
			   gc=0;
			   xgcd(a,b);
			   pw.println(a+"*"+x+" + "+b+"*"+y+" = "+gc);
			   
		   }
		   
		   
		   public static long modex(long a, long b, long c)
		   {
			   if(b==0)
				   return 1;
			   else if(b==1)
				   return a%c;
			   else if(b%2==0)
			   {
				   	return modex((a*a)%c,b/2,c);
			   }
			   else
			   {
				   return (a*modex((a*a)%c,b/2,c))%c;
				   
			   }
			   
			   
		   }
		   
		   
		   public static void xgcd(int a, int b)
		   {
			   
			   if(b==0)
			   {
				   x=1;
				   y=0;
				   gc=a;
				   
				   
			   }
			   else
			   {
				   xgcd(b,a%b);
				   int temp = x;
				   x=y;
				   y = temp - ((a/b)*y);
				   
			   }
		   }
		   
		   public int gcd(int a, int b)
		   {
			   if(b==0)return a;
			   else return gcd(b,a%b);
			   
		   }
		   
		   static int x,y,gc;
		   
		  
		
		   
		   static HashSet<Character> set;
		   
		   
		   
		   public static int expmod(int a, int b, int mod)
		   {
			   if(b==0)return 1;
			   if(b==1)return a;
			   
			   if(b%2==0)
			   {
				   return ((expmod(a,b/2,mod)%mod)*(expmod(a,b/2,mod)%mod))%mod;
			   }
			   else
			   {
				   return ((a%mod)*(expmod(a,b/2,mod)%mod)*(expmod(a,b/2,mod)%mod))%mod;
			   }
		   }
		   
		   
		   
		   public static void main(String[] args) 
	   {
			//a=97
			   
			 
			   
			   int n = sc.nextInt();
			   int k = sc.nextInt();
			   
			   String st = sc.nextLine();
			   
			   int[] alp = new int[26];
			   
			   for(int i=0;i<st.length();i++)
			   {
				   char ch = st.charAt(i);
				   int f = ch-97;
				   alp[f]++;
			   }
			  
			   if(k>n)
			   {
				   int f=-1;
				   
				   for(int i=0;i<26;i++)
				   {
					   if(alp[i]!=0)
					   {
						   f=i; break;
					   }
				   }
				   char ex = (char) (f+97);
				   
				  // while(st.length()!=k)st=st+ex;
				   char[] ans = new char[k];
				  char ref[] = st.toCharArray();
				   
				  for(int i=0;i<k;i++)
				   {
					   if(i<n)
					   {
						   ans[i]=ref[i];
					   }
					   else
					   {
						   ans[i]=ex;
					   }
				   }
				  
				  for(int i=0;i<k;i++)pw.print(ans[i]);
				   
				  // pw.println(st);
				   
			   }
			   else
			   {
				   
				   char[] org = st.toCharArray();
				   int si=-1;
				   
				   for(int i=k-1;i>=0;i--)
				   {
					   int lc = st.charAt(i)-97;
					   
					  int fd=0;
					   char r=' ';
					   for(int j=lc+1;j<26;j++)
					   {
						   if(alp[j]>0)
						   {
							   r = (char) (j+97);
							   fd=1;
							   break;
						   }
					   }
					   
					   if(fd==1)
					   {
						   org[i]=r;
						   si=i;
						   break;
					   }
				   }
					   
				   int sm=0;
				   
				   for(int i=0;i<26;i++)
				   {
					   if(alp[i]>0)
					   {
						   sm=i;
						   break;
					   }
				   }
				   
				   char smc = (char) (sm+97);
				   
				   
				   for(int j=si+1;j<k;j++)
				   {
					   org[j]=smc;
				   }
				   
			  
				   for(int i=0;i<k;i++)pw.print(org[i]);
				   
				   
				   
			   }
			   
			   
			   
			   
			   
			pw.close();   
			   
	   }
		
			
		   
		   
		   
		   
		   
		   
		   static  class MyScanner 
			{
	
			BufferedReader br;
			StringTokenizer st;
	
			public MyScanner() 
			{
				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;
			}
	
		}
	
		static MyScanner sc = new  MyScanner();
		static PrintWriter pw = new PrintWriter(System.out, true);
		
	
	
		
	} 