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.*;
import java.lang.*;
import java.math.*;
public class C {
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        // Scanner scan = new Scanner(System.in);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        // int n = Integer.parseInt(bf.readLine());
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        String s = bf.readLine();
        int[] a = new int[k];
        boolean[] exists = new boolean[26];
        int[] val = new int[26];
        int cur = 0;

        for(int i=0; i<n; i++)
          exists[s.charAt(i)-'a'] = true;
        for(int i=0; i<26; i++) {
          if(exists[i]) {
            val[i] = cur;
            cur++;
          }
        }
        int base = cur;
        int[] backwards = new int[base];
        for(int i=0; i<26; i++) if(exists[i]) backwards[val[i]] = i;
        if(n < k) {
          StringBuilder sb = new StringBuilder();
          sb.append(s);
          for(int i=0; i<k-n; i++) sb.append((char)(backwards[0]+'a'));
          out.println(sb.toString());
        }
        else {

          for(int i=0; i<k; i++)
            a[i] = val[s.charAt(i)-'a'];
          for(int i=k-1; i>=0; i--) {
            a[i]++;
            if(a[i] == base)
              a[i] = 0;
            else break;
          }
          StringBuilder sb = new StringBuilder();
          for(int i=0; i<k; i++) sb.append((char)(backwards[a[i]]+'a'));
          out.println(sb.toString());


        }
        // int[] a = new int[n];
        // for(int i=0; i<n; i++) a[i] =  Integer.parseInt(st.nextToken());

        out.close(); System.exit(0);
    }


}
