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 CF940C {
	public static void main(String[] args) {
		//System.out.println("hi 940C");
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int k = in.nextInt();
        
        String s = in.next();
//        System.out.println(s);
//        System.out.println(N);
//        System.out.println(k);

        int L = 26;
        boolean letters[] = new boolean[L];
        for (int i = 0; i < L; i++) {
        	letters[i] = false;
        }
        for (int i = 0; i < N; i++) {
        	char c = s.charAt(i);
        	letters[c - 'a'] = true;
        }
        
        int i = 0; 
    	while (!letters[i]) {
    		i++;
    	}
    	char first = (char) ('a' + i);
    	
    	i = L - 1;
    	while (!letters[i]) {
    		i--;
    	}
    	char last = (char) ('a' + i);
          

        if (k > N) {
        	StringBuilder builder = new StringBuilder();
        	for (int r = 0; r < k - N; r++) {
        	    builder.append(first);
        	}
        	String lastPart = builder.toString();
        	
        	String result = s + lastPart;
        	System.out.println(result);
        } else {
        	i = k - 1;
        	while (s.charAt(i) == last) i--;
        	char toChange = s.charAt(i);
        	String firstPart = s.substring(0, i);
        	StringBuilder builder = new StringBuilder();
        	for (int r = 0; r < k - i - 1; r++) {
        	    builder.append(first);
        	}
        	String lastPart = builder.toString();
        	
        	int pos = toChange - 'a' + 1;
        	while (!letters[pos]) pos++;
        	String result = firstPart + ((char)(pos + 'a')) + lastPart;
        	System.out.println(result);
        }
	}
}
