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.util.Scanner;
public class C940{
	static char next(int c[],char a){
		int i=a-'a';
		while(true){
			i=(i+1)%26;
			if(c[i]!=0)
				return (char)(i+'a');
		}
		
	}
	public static void main(String args[]){
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int k=sc.nextInt();
		char s[]=(sc.next()).toCharArray();
		int c[]=new int[26];
		for(int i=0;i<n;i++){
			c[s[i]-'a']++;
		}
		char r[]=new char[k];
		for(int i=0;i<Math.min(k,n);i++)
			r[i]=s[i];
		if(k>n){
			char ch=next(c,'z');
			for(int i=n;i<k;i++)
				r[i]=ch;
			System.out.println((new String(r)));
		}
		else{
		//r[k]='z';
		int f=0;
		for(int i=k-1;i>=0;i--){
			char b=next(c,r[i]);
			
			if(b>r[i]){
				
				r[i]=b;
				
				f=1;
				break;
			}
			r[i]=b;
		}
		System.out.println((new String(r)));
		}
	}
} 