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;
template <class T, class U>
inline void relax_min(T &a, U b) {
  a = min(a, b);
}
template <class T, class U>
inline void relax_max(T &a, U b) {
  a = max(a, b);
}
template <typename T>
inline bool updmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
inline bool updmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <class T, class U>
istream &operator>>(istream &in, pair<T, U> &a) {
  in >> a.first >> a.second;
  return in;
}
template <class T, class U>
ostream &operator<<(ostream &out, const pair<T, U> &a) {
  out << a.first << ' ' << a.second;
  return out;
}
template <class T>
istream &operator>>(istream &in, vector<T> &a) {
  for (decltype(0)((i)) = (0); ((i)) < ((((int)(a).size()))); ++((i)))
    in >> a[i];
  return in;
}
template <class T>
ostream &operator<<(ostream &out, const vector<T> &a) {
  for (decltype(0)((i)) = (0); ((i)) < ((((int)(a).size()))); ++((i)))
    out << a[i] << ' ';
  return out;
}
int next_int() {
  int(tmp);
  scanf("%d", &(tmp));
  return tmp;
}
long long next_ll() {
  long long(tmp);
  scanf("%lld", &(tmp));
  return tmp;
}
long long modPow(long long a, long long b, long long MOD) {
  long long ret = 1;
  for (; b; b >>= 1) {
    if (b & 1)
      ret = ((((((long long)(ret) * (long long)(a))) % ((MOD))) + ((MOD))) %
             ((MOD)));
    a = ((((((long long)(a) * (long long)(a))) % ((MOD))) + ((MOD))) % ((MOD)));
  }
  return ret;
}
const long long EXACTLY_ONE_HUNDRED = 100;
const long long EXACTLY_ONE_THOUSAND = 1000;
const long long EXACTLY_ONE_MILLION = 1000 * 1000;
const long long EXACTLY_ONE_BILLION =
    EXACTLY_ONE_THOUSAND * EXACTLY_ONE_MILLION;
const int MAXN1 = (int)(EXACTLY_ONE_HUNDRED * EXACTLY_ONE_THOUSAND) + 3;
const int MAXN2 = (int)(2 * EXACTLY_ONE_HUNDRED * EXACTLY_ONE_THOUSAND) + 3;
const int MAXN3 = (int)(3 * EXACTLY_ONE_HUNDRED * EXACTLY_ONE_THOUSAND) + 3;
const int MAXN4 = (int)(4 * EXACTLY_ONE_HUNDRED * EXACTLY_ONE_THOUSAND) + 3;
const int MAXN5 = (int)(5 * EXACTLY_ONE_HUNDRED * EXACTLY_ONE_THOUSAND) + 3;
const int MAXN = MAXN3;
const int INF = (int)EXACTLY_ONE_BILLION + 7;
const int INF2 = 1 << 30;
const long long INFLL = 4LL * EXACTLY_ONE_BILLION * EXACTLY_ONE_BILLION + 7;
const long long INFLL2 = 1LL << 60;
const long double Pi = acos(-1.0);
const long double EPS = 1e-7;
const int MOD = (int)EXACTLY_ONE_BILLION + 7;
int main() {
  int(n), (k);
  scanf("%d%d", &((n)), &((k)));
  string t;
  cin >> t;
  int alph[26] = {}, maxa{-1}, mina{27};
  for (auto c : t) {
    alph[c - 'a'] = 1;
    updmax(maxa, c - 'a');
    updmin(mina, c - 'a');
  }
  string s;
  if (k <= n) {
    s = t.substr(0, k);
    n = k;
  } else {
    s = t + string(k - n, mina + 'a');
    cout << s << endl;
    return 0;
  }
  int j = n - 1;
  for (; s[j] == maxa + 'a'; --j) {
  }
  for (decltype(0)((i)) = (0); ((i)) < ((26)); ++((i))) {
    if (alph[i] && i > s[j] - 'a') {
      s[j] = i + 'a';
      for (decltype(j + 1)(q) = (j + 1); (q) < (n); ++(q)) {
        s[q] = mina + 'a';
      }
      break;
    }
  }
  cout << s << endl;
  return 0;
}
