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>
#pragma GCC optimize("Ofast")
using namespace std;
const long long MAX = 1e18 + 1;
const double pi = 3.1415926535897932384626433832;
const long long M = 1e9 + 7;
long long modpow(long long x, long long n, long long mod1) {
  if (n == 0) return 1 % mod1;
  long long u = modpow(x, n / 2, mod1);
  u = (u * u) % mod1;
  if (n % 2 == 1) u = (u * x) % mod1;
  return u;
}
long long POW(long long x, long long y) { return modpow(x, y, LONG_LONG_MAX); }
long long bis(long long a[], long long l, long long r, long long x) {
  while (l <= r) {
    long long m = l + (r - l) / 2;
    if (a[m] == x) return m;
    if (a[m] < x)
      l = m + 1;
    else
      r = m - 1;
  }
  return -1;
}
long long gcd(long long x, long long y) {
  if (x == 0)
    return y;
  else
    return gcd(y % x, x);
}
long long lcm(long long x, long long y) { return (x * y) / gcd(x, y); }
bool isPrime(long long n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long i = 5; i * i <= n; i = i + 6) {
    if (n % i == 0 || n % (i + 2) == 0) {
      return false;
    }
  }
  return true;
}
bool pdrome(string s) {
  long long n = s.length();
  for (long long i = 0; i < n / 2; i++) {
    if (s[i] != s[n - i - 1]) {
      return false;
    }
  }
  return true;
}
long long fac[10] = {1};
void fact() {
  for (long long i = 1; i < 10; i++) {
    fac[i] = fac[i - 1] * i;
  }
}
bool sumdigits(long long a) {
  long long result = 0;
  while (a > 0) {
    result += a % 10;
    a /= 10;
  }
  return result;
}
long long digits(long long n) { return floor(log10(n) + 1); }
const long long Node = 1e5 + 7;
vector<long long> adj[Node];
bool vis[Node] = {false};
void addedge(long long u, long long v) {
  adj[u].push_back(v);
  adj[v].push_back(u);
}
void bfs(long long u) {
  vis[u] = true;
  list<long long> q;
  q.push_back(u);
  while (!q.empty()) {
    q.pop_front();
    for (auto x : adj[u]) {
      if (!vis[x]) {
        vis[x] = true;
        q.push_back(x);
      }
    }
  }
}
void dfs(long long u) {
  vis[u] = true;
  cout << u << " ";
  for (auto x : adj[u]) {
    if (!vis[x]) {
      dfs(x);
    }
  }
}
long long con1(string s) {
  long long res = 0;
  stringstream geek(s);
  geek >> res;
  return res;
}
string con2(long long num) {
  string stri = to_string(num);
  return stri;
}
long long countbits(long long k) {
  long long cnt = log2(k);
  return cnt;
}
long long ncr(long long n, long long r) {
  if (r > n || r < 0) return 0;
  long long ans = 1, cnt = 1;
  for (long long x = n; x > r; x--) {
    ans = ((ans % M) * (x % M)) % M;
    ans = (ans / cnt) % M;
    ans = ans % M;
    cnt++;
  }
  return ans % M;
}
long long Pnc(int n, int k) {
  long long P = 1;
  for (int i = 0; i < k; i++) P *= (n - i) % M;
  return P % M;
}
long long modInverse(long long a, long long m) {
  long long m0 = m;
  long long y = 0, x = 1;
  if (m == 1) return 0;
  while (a > 1) {
    long long q = a / m;
    long long t = m;
    m = a % m, a = t;
    t = y;
    y = x - q * y;
    x = t;
  }
  if (x < 0) x += m0;
  return x;
}
char chk(char c) {
  if (c == '1') return '0';
  return '1';
}
void solve() {
  long long n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  if (k > n) {
    char c = *min_element(s.begin(), s.end());
    cout << s;
    for (long long i = 0; i < k - n; i++) {
      cout << c;
    }
    return;
  }
  set<char> s1;
  for (long long i = 0; i < s.size(); i++) {
    s1.insert(s[i]);
  }
  string res = s.substr(0, k);
  char ck = '*', c = *(s1.begin());
  long long ok = 0;
  for (long long i = k - 1; i >= 0; i--) {
    char cn = *s1.upper_bound(res[i]);
    if (s1.count(cn) == 0) {
      res[i] = c;
    } else {
      res[i] = cn;
      ok = 1;
      break;
    }
  }
  if (ok) {
    cout << res << endl;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  long long t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
