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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class ProblemC {
  public static void main(String[] args)throws IOException {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    String[] strs = reader.readLine().split(" ");
    int n = Integer.parseInt(strs[0]);
    int k = Integer.parseInt(strs[1]);
    String s = reader.readLine();

    ArrayList<Integer>[] index = new ArrayList[256];
    Set<Character> set = new HashSet<>();
    initSet(set, s);
    initIndex(index, set, s);
    StringBuilder builder = new StringBuilder();
    char minChar = getMinChar(set);
    boolean putMinChar = false;
    for(int i = 0; i < k; i++){
      if(putMinChar || i >= s.length()){
        builder.append(minChar);
        continue;
      }
      if(k > n || canPutChar(index, i, k)){
        builder.append(s.charAt(i));
      }else{
        builder.append(getNextGreaterCharacter(s.charAt(i), set));
        putMinChar = true;
      }
    }
    System.out.println(builder.toString());
  }

  private static void initSet(Set<Character> set, String s){
    for(char c: s.toCharArray()){
      set.add(c);
    }
  }

  private static void initIndex(ArrayList<Integer>[] index, Set<Character> set, String s){
    for(char a = 'a' ; a <= 'z'; a++){
      if(!set.contains(a)){
        continue;
      }
      for(int i = 0; i < s.length(); i++){
        if(a > s.charAt(i)){
          if(index[a] == null){
            index[a] = new ArrayList<>();
          }
          index[a].add(i);
        }
      }
    }
  }

  private static char getMinChar(Set<Character> set){
    char ret = 'z';
    for(char a: set){
      if(a < ret){
        ret = a;
      }
    }
    return ret;
  }

  private static boolean canPutChar(ArrayList<Integer>[] index, int i, int k){
    for(char a = 'a'; a <= 'z'; a++){
      if(index[a] != null) {
        int idx = binSearch(index, i, a);
        if(idx != -1 && idx > i && idx < k){
          return true;
        }
      }
    }
    return false;
  }

  private static int binSearch(ArrayList<Integer>[] index, int i, char a){
    if(index[a].get(index[a].size() - 1) <= i){
      return -1;
    }

    int low = 0;
    int high = index[a].size() - 1;
    while(low <= high){
      int mid = (low + high) / 2;
      if(index[a].get(mid) <= i){
        low = mid + 1;
      }else{
        high = mid - 1;
      }
    }
    return index[a].get(low);
  }

  private static char getNextGreaterCharacter(char a, Set<Character> set){
    char ret = 'z';
    for(char c: set){
      if(c > a){
        ret = (char) Math.min(ret, c);
      }
    }
    return ret;
  }
}
