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 pack;

//import java.util.Arrays;
import java.util.Scanner;

public class first
{	
	public static int[] func(String str,boolean[] arr,char[] alpha)
	{	
		for(int i=str.length()-1;i>=0;i--)
		{	for(int j=1;j<=26;j++)
			{	int a=(int) str.charAt(i);
				int b=(int) alpha[j];
				if(arr[j] && a<b)
				{	return new int[]{i,(int) alpha[j]};
				}	
			}
		}
		return new int[]{0,(int) str.charAt(0)};
		
	}
	public static void main(String[] args)
	{	Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int k=sc.nextInt();
		String str=sc.next();
		boolean[] arr=new boolean[27];
		char[] alpha={'.','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
		int min=Integer.MAX_VALUE;
		for(int i=0;i<str.length();i++)
		{	arr[((int) str.charAt(i))-96]=true;
			min=Math.min((int) str.charAt(i), min);
		}
		char append=(char) min;
		
		if(n>=k)
		{	int[] result=func(str.substring(0,k),arr,alpha);
			int index=result[0];
			char maybe=(char) result[1];
			System.out.print(str.substring(0,index));
			System.out.print(maybe);
			for(int i=0;i<k-index-1;i++)
				System.out.print(append);
		}
		else
		{	System.out.print(str);
			for(int i=0;i<k-str.length();i++)
				System.out.print(append);
		}
	}
}