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.
#include <bits/stdc++.h>
using namespace std;
bool debug = 0;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
string direc = "RDLU";
long long ln, lk, lm;
void etp(bool f = 0) {
  puts(f ? "YES" : "NO");
  exit(0);
}
void addmod(int &x, int y, int mod = 1000000007) {
  assert(y >= 0);
  x += y;
  if (x >= mod) x -= mod;
  assert(x >= 0 && x < mod);
}
void et() {
  puts("-1");
  exit(0);
}
long long fastPow(long long x, long long y, int mod = 1000000007) {
  long long ans = 1;
  while (y > 0) {
    if (y & 1) ans = (x * ans) % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
long long gcd1(long long x, long long y) {
  long long z = y;
  while (x % y != 0) {
    z = x % y;
    x = y;
    y = z;
  }
  return z;
}
char s[100005];
bool vis[30];
void fmain(int ID) {
  scanf("%d%d", &n, &k);
  scanf("%s", s + 1);
  for (int(i) = 1; (i) <= (int)(n); (i)++) vis[s[i] - 'a'] = 1;
  if (n < k) {
    for (int(i) = 1; (i) <= (int)(n); (i)++) printf("%c", s[i]);
    for (int(j) = 0; (j) < (int)(26); (j)++)
      if (vis[j]) {
        for (int(cc) = 0; (cc) < (int)(k - n); (cc)++) printf("%c", 'a' + j);
        break;
      }
    return;
  }
  for (int i = k; i; i--) {
    for (int j = (s[i] - 'a') + 1; j < 26; j++)
      if (vis[j]) {
        for (int(z) = 1; (z) <= (int)(i - 1); (z)++) printf("%c", s[z]);
        printf("%c", 'a' + j);
        for (int(tar) = 0; (tar) < (int)(26); (tar)++)
          if (vis[tar]) {
            for (int z = i + 1; z <= k; z++) printf("%c", 'a' + tar);
            return;
          }
        return;
      }
  }
}
int main() {
  int t = 1;
  for (int(i) = 1; (i) <= (int)(t); (i)++) {
    fmain(i);
  }
  return 0;
}
