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.*;
import java.io.*;

public class File {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt(); // Length of s 
		int k = sc.nextInt(); // Required length of t
		char[] s = sc.next().toCharArray();
		
		// If t is longer than s, 
		// we can match the entire prefix of s, 
		// then just add the smallest character of s to the end.
		TreeSet<Character> set = new TreeSet<>();
		
		char minChar = s[0];
		for (int i = 0; i < n; i++) {
			set.add(s[i]);
			
			if (s[i] < minChar) {
				minChar = s[i];
			}
		}
	
		if (k > n) {
			StringBuilder sb = new StringBuilder();
			sb.append(new String(s));
			
			for (int i = 0; i < k - n; i++) {
				sb.append(minChar);
			}
			
			System.out.println(sb.toString());
			return;
		}
		
		// Store the smallest character greater than a character in the set.
		List<Character> list = new ArrayList<>();
		for (char c : set) {
			list.add(c);
		}
		char[] greater = new char[26];
		char greaterToRight = list.get(list.size() - 1);
				
		for (int i = list.size() - 1; i >= 0; i--) {
			char c = list.get(i);
			
			greater[c-'a'] = greaterToRight;
			
			if (c < greaterToRight) {
				greaterToRight = c;
			}
		}
		
		// Change the rightmost character to the next greater character in the set.
		// Change all characters to right of that to the smallest character.
		int updateIndex = k - 1;
		while (updateIndex >= 0) {
			char c = s[updateIndex];
			
			// We can replace this character with something greater than it.
			if (greater[c-'a'] != c) {
				break;
			}
			
			updateIndex--;
		}
		
		char updateChar = s[updateIndex];
		s[updateIndex] = greater[updateChar-'a'];
		
		for (int i = updateIndex + 1; i < k; i++) {
			s[i] = minChar;
		}
		
		System.out.println(new String(s).substring(0, k));
	}
}