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;
const long long Nfact = 200005;
const long long mod = 1000000007;
const long long Nsieve = 1000005;
vector<bool> is_prime(Nsieve, true);
void sieve() {
  is_prime[0] = is_prime[1] = false;
  for (long long i = 2; i * i <= Nsieve; i++) {
    if (is_prime[i]) {
      for (long long j = i * i; j <= Nsieve; j += i) is_prime[j] = false;
    }
  }
}
long long bSearch(long long l, long long r, long long x,
                  vector<long long> arr) {
  while (l <= r) {
    long long m = l + (r - l) / 2;
    if (arr[m] == x) return m;
    if (arr[m] < x)
      l = m + 1;
    else
      r = m - 1;
  }
  return -1;
}
void primeFactors(long long n) {
  while (n % 2 == 0) {
    n = n / 2;
  }
  for (long long i = 3; i <= sqrt(n); i += 2) {
    while (n % i == 0) {
      n = n / i;
    }
  }
  if (n > 2) cout << n << " ";
}
long long power(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long modulo(long long a, long long b) {
  long long c = a % b;
  return (c < 0) ? c + b : c;
}
long long mul(long long x, long long y) { return (x * y) % mod; }
long long inv(long long x) { return power(x, mod - 2, mod); }
long long divide(long long x, long long y) { return mul(x, inv(y)); }
long long fact[Nfact];
void precalc() {
  fact[0] = 1;
  for (long long i = 1; i < Nfact; i++) fact[i] = mul(fact[i - 1], i);
}
long long nCr(long long n, long long k) {
  if (n < k) return 0;
  return divide(fact[n], mul(fact[k], fact[n - k]));
}
void solve() {
  long long n, k;
  cin >> n >> k;
  string s, str;
  cin >> s;
  str = s;
  set<char> se;
  for (long long i = 0; i < n; i++) {
    se.insert(s[i]);
  }
  auto it = se.begin();
  if (k > n) {
    s.append(k - n, *it);
  } else {
    for (long long i = k - 1; i >= 0; i--) {
      auto it3 = se.find(s[i]);
      ++it3;
      if (it3 != se.end()) {
        s[i] = *it3;
        break;
      } else {
        s[i] = *it;
        continue;
      }
    }
  }
  cout << s.substr(0, k) << endl;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long t = 1;
  while (t--) {
    solve();
  }
  cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl;
  return 0;
}
