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.*;
import java.text.*;
import java.lang.*;
import java.math.BigInteger;
import java.util.regex.*;
public class Myclass {
		public static ArrayList a[]=new ArrayList[200001];
		static boolean visited[]=new boolean [200001];
		static int idx[]=new int[200001];
		static int number[]=new int[200001];

		static HashMap<Integer,Integer>hm=new HashMap<>();
		static int cnt=0;
		static void dfs(int n)
		{
			int x=0;
			visited[n]=true;
			cnt++;
			hm.put(cnt,n );
			idx[n]=cnt;
			for(int i=0;i<a[n].size();i++)
			{
				int idx=(int) a[n].get(i);
				if(!visited[idx])
				{
					dfs(idx);
				}
			}
			number[n]=cnt-idx[n];
		}
		
		public static void main(String[] args) throws InterruptedException
		{
		    InputReader in = new InputReader(System.in);
			PrintWriter pw = new PrintWriter(System.out);
			int n=in.nextInt();
			int m=in.nextInt();
			char s[]=in.nextLine().toCharArray();
			TreeSet<Character>tr=new TreeSet<>();
			for(int i=0;i<n;i++)
			{
				tr.add(s[i]);
			}
			Vector<Character>v=new Vector<>(tr);
			if(m>n)
			{
				for(int i=0;i<n;i++)
				{
					pw.print(s[i]);
				}
				for(int i=n;i<m;i++)
				{
					pw.print(v.get(0));
				}
			}
			else
			{
				int idx=-1;
				for(int i=m-1;i>=0;i--)
				{
					if(s[i]==v.get(v.size()-1))
						continue;
					idx=i;
					break;
				}
				int idx2=-1;
				for(int i=0;i<v.size();i++)
				{
					if(s[idx]==v.get(i))
					{
						idx2=i;
						break;
					}
				}
				for(int i=0;i<idx;i++)
					pw.print(s[i]);
				pw.print(v.get(idx2+1));
				for(int i=idx+1;i<m;i++)
					pw.print(v.get(0));
				
			}
			pw.flush();
			pw.close();
		}
		
		static class InputReader 
		{
		private final InputStream stream;
		private final byte[] buf = new byte[8192];
		private int curChar, snumChars;
		private SpaceCharFilter filter;
 
		public InputReader(InputStream stream) 
		{
			this.stream = stream;
		}
		public int snext() 
		{
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars) 
			{
				curChar = 0;
				try 
				{
					snumChars = stream.read(buf);
				} 
				catch (IOException e) 
				{
					throw new InputMismatchException();
				}
				
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
 
		public int nextInt() 
	    {
			int c = snext();
			while (isSpaceChar(c)) 
			{
				c = snext();
			}
			int sgn = 1;
			if (c == '-')
		    {
				sgn = -1;
				c = snext();
			}
			int res = 0;
			do 
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
 
		public long nextLong()
	    {
			int c = snext();
			while (isSpaceChar(c)) 
			{
				c = snext();
			}
			int sgn = 1;
			if (c == '-') 
			{
				sgn = -1;
				c = snext();
			}
			long res = 0;
			do 
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
 
		public int[] nextIntArray(int n) 
		{
			int a[] = new int[n];
			for (int i = 0; i < n; i++) 
			{
				a[i] = nextInt();
			}
			return a;
		}
		static class tri implements Comparable<tri> {
			int p, c, l;
 
			tri(int p, int c, int l) {
				this.p = p;
				this.c = c;
				this.l = l;
			}
 
			public int compareTo(tri o) {
				return Integer.compare(l, o.l);
			}
		}
 
		public String readString()
	    {
			int c = snext();
			while (isSpaceChar(c)) 
			{
				c = snext();
			}
			StringBuilder res = new StringBuilder();
			do 
			{
				res.appendCodePoint(c);
				c = snext();
			} while (!isSpaceChar(c));
			return res.toString();
		}
 
		public String nextLine() 
		{
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			StringBuilder res = new StringBuilder();
			do 
			{
				res.appendCodePoint(c);
				c = snext();
			} while (!isEndOfLine(c));
			return res.toString();
		}
 
		public boolean isSpaceChar(int c) 
		{
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
 
		private boolean isEndOfLine(int c) 
		{
			return c == '\n' || c == '\r' || c == -1;
		}
 
		public interface SpaceCharFilter
	    {
			public boolean isSpaceChar(int ch);
		}
	}
		public static long mod = 1000000007;
		public static int d;
		public static int p;
		public static int q;
		
		public static int[] suffle(int[] a,Random gen)
		{
			int n = a.length;
			for(int i=0;i<n;i++)
			{
				int ind = gen.nextInt(n-i)+i;
				int temp = a[ind];
				a[ind] = a[i];
				a[i] = temp;
			}
			return a;
		}
		
		public static void swap(int a, int b){
			int temp = a;
			a = b;
			b = temp;
		}
		
		public static HashSet<Integer> primeFactorization(int n)
		{
			HashSet<Integer> a =new HashSet<Integer>();
			for(int i=2;i*i<=n;i++)
			{
				while(n%i==0)
				{
					a.add(i);
					n/=i;
				}
			}
			if(n!=1)
				a.add(n);
			return a;
		}
		
		public static void sieve(boolean[] isPrime,int n)
		{
			for(int i=1;i<n;i++)
				isPrime[i] = true;
			
			isPrime[0] = false;
			isPrime[1] = false;
			
			for(int i=2;i*i<n;i++)
			{
				if(isPrime[i] == true)
				{
					for(int j=(2*i);j<n;j+=i)
						isPrime[j] = false;
				}
			}
		}
		
		public static int GCD(int a,int b)
		{
			if(b==0)
				return a;
			else
				return GCD(b,a%b);
		}
		
		public static long GCD(long a,long b)
		{
			if(b==0)
				return a;
			else
				return GCD(b,a%b);
		}
		
		public static void extendedEuclid(int A,int B)
		{
			if(B==0)
			{
				d = A;
				p = 1 ;
				q = 0;
			}
			else
			{
				extendedEuclid(B, A%B);
				int temp = p;
				p = q;
				q = temp - (A/B)*q;
			}
		}
		
		public static long LCM(long a,long b)
		{
			return (a*b)/GCD(a,b);
		}
		
		public static int LCM(int a,int b)
		{
			return (a*b)/GCD(a,b);
		}
		
		public static int binaryExponentiation(int x,int n)
		{
		    int result=1;
		    while(n>0)
		    {
		        if(n % 2 ==1)
		            result=result * x;
		        x=x*x;
		        n=n/2;
		    }
		    return result;
		}
		
		public static long binaryExponentiation(long x,long n)
		{
		    long result=1;
		    while(n>0)
		    {
		        if(n % 2 ==1)
		            result=result * x;
		        x=x*x;
		        n=n/2;
		    }
		    return result;
		}
		
		public static int modularExponentiation(int x,int n,int M)
		{
		    int result=1;
		    while(n>0)
		    {
		        if(n % 2 ==1)
		            result=(result * x)%M;
		        x=(x%M*x)%M;
		        n=n/2;
		    }
		    return result;
		}
		public static long me(long x,long n,long M)
		{
		    long result=1;
		    while(n>0)
		    {
		        if(n % 2 ==1)
		            result=(result%M * x%M)%M;
		        x=(x%M * x%M)%M;
		    }
		    return result;
		}
		
		public static long modularExponentiation(long x,long n,long M)
		{
		    long result=1;
		    while(n>0)
		    {
		        if(n % 2 ==1)
		            result=(result%M * x%M)%M;
		        x=(x%M * x%M)%M;
		        n=n/2;
		    }
		    return result;
		}
		
		public static long modInverse(int A,int M)
		{
		    return modularExponentiation(A,M-2,M);
		}
		
		public static long modInverse(long A,long M)
		{
		    return me(A,M-2,M);
		}
		
		public static boolean isPrime(int n)
		{
		    
		    if (n <= 1)  return false;
		    if (n <= 3)  return true;
		    
		    if (n%2 == 0 || n%3 == 0) 
		    	return false;
		 
		    for (int i=5; i*i<=n; i=i+6)
		    {
		        if (n%i == 0 || n%(i+2) == 0)
		           return false;
		    }
		    
		    return true;
		}
		
		 public static long[] shuffle(long[] a, Random gen){ 
		        for(int i = 0, n = a.length;i < n;i++){ 
		            int ind = gen.nextInt(n-i)+i; 
		            long d = a[i]; 
		            a[i] = a[ind]; 
		            a[ind] = d; 
		        } 
		        return a; 
		    }
		static class pair implements Comparable<pair>
		{
			Integer x;
			Integer y;
			pair(int a,int m)
			{
				this.x=a;
				this.y=m;
			}
			
 
			
 
 
		public boolean isEmpty() {
				// TODO Auto-generated method stub
				return false;
			}
 
 
 
 
 
		public int compareTo(pair o) {
				int result = x.compareTo(o.x);
				if(result==0)
					result = y.compareTo(o.y);
				
			return result;
			}  
			
			public String toString()
			{
				return x+" "+y;
			}
			
			public boolean equals(Object o)
			{
				if (o instanceof pair)
			    {
					pair p = (pair)o;
					return p.x == x && p.y == y ;
				}
				return false;
			}
			
			public int hashCode()
			{
				return new Long(x).hashCode()*31 + new Long(y).hashCode();
			}
		}
} 