#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (long long i = 0; i < static_cast<long long>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
using ll = long long;
const long long MAXN = 1005;
char s[MAXN];
namespace Hash {
const long long base1 = 131;
const long long base2 = 233;
const long long MOD1 = 1e9 + 7;
const long long MOD2 = 1e9 + 9;
long long p1[MAXN], p2[MAXN], h1[MAXN], h2[MAXN];
void init(char s[], long long n) {
  p1[0] = p2[0] = 1;
  h1[0] = h2[0] = 0;
  for (long long i = 1; i <= n; i++) {
    p1[i] = (p1[i - 1] * base1) % MOD1;
    p2[i] = (p2[i - 1] * base2) % MOD2;
    h1[i] = (h1[i - 1] * base1 + s[i]) % MOD1;
    h2[i] = (h2[i - 1] * base2 + s[i]) % MOD2;
  }
}
long long getHash(long long l, long long r) {
  long long H1 = ((h1[r] - h1[l - 1] * p1[r - l + 1]) % MOD1 + MOD1) % MOD1;
  long long H2 = ((h2[r] - h2[l - 1] * p2[r - l + 1]) % MOD2 + MOD2) % MOD2;
  return H1 * MOD2 + H2;
}
}  // namespace Hash
vector<pair<long long, long long>> ord;
long long n, m, rk[MAXN], lcp[MAXN][MAXN];
long long k, dp[MAXN][MAXN], dp1[MAXN][MAXN], dp2[MAXN][MAXN];
bool cmp(long long l1, long long r1, long long l2, long long r2) {
  long long len1 = r1 - l1 + 1, len2 = r2 - l2 + 1;
  bool ret;
  if (lcp[l1][l2] >= min(len1, len2)) {
    ret = len1 < len2;
  } else {
    ret = rk[l1] < rk[l2];
  }
  return ret;
};
bool check(long long first) {
  memset(dp, 0, sizeof(dp));
  vector<long long> to(n + 1);
  for (long long i = 0; i <= n; i++) to[i] = i + 1;
  for (long long i = first; i < ((long long)ord.size()); i++) {
    to[ord[i].first - 1] = max(to[ord[i].first - 1], ord[i].second + 1);
  }
  dp[0][0] = 1;
  for (long long j = 0; j <= m; j++) {
    if (j)
      for (long long i = 1; i <= n; i++) {
        dp[i][j] += dp[i - 1][j];
        if (dp[i][j] > k) dp[i][j] = k;
      }
    for (long long i = j; i <= n; i++) {
      if (to[i] <= n) {
        dp[to[i]][j + 1] += dp[i][j];
        if (dp[to[i]][j + 1] > k) {
          dp[to[i]][j + 1] = k;
        }
      }
    }
  }
  return dp[n][m] < k;
}
long long suck[MAXN];
void my_main() {
  cin >> n >> m >> k;
  cin >> (s + 1);
  Hash::init(s, n);
  for (long long i = 1; i <= n; i++) {
    for (long long j = i; j <= n; j++) {
      ord.push_back({i, j});
    }
  }
  for (long long i = 1; i <= n; i++) suck[i] = i;
  auto fuck = [&](long long first, long long second) {
    string s1, s2;
    for (long long i = first; i <= n; i++) s1 += s[i];
    for (long long i = second; i <= n; i++) s2 += s[i];
    return s1 < s2;
  };
  sort(suck + 1, suck + n + 1, fuck);
  for (long long i = 1; i <= n; i++) rk[suck[i]] = i;
  for (long long i = 1; i <= n; i++) {
    for (long long j = 1; j <= n; j++) {
      long long l = 1, r = min(n - i + 1, n - j + 1);
      while (r - l > 1) {
        long long mid = (l + r) / 2;
        if (Hash::getHash(i, i + mid - 1) == Hash::getHash(j, j + mid - 1)) {
          l = mid;
        } else {
          r = mid;
        }
      }
      if (Hash::getHash(i, i + r - 1) == Hash::getHash(j, j + r - 1)) {
        lcp[i][j] = r;
      } else if (Hash::getHash(i, i + l - 1) == Hash::getHash(j, j + l - 1)) {
        lcp[i][j] = l;
      } else {
        assert(l == 1);
        lcp[i][j] = 0;
      }
    }
  }
  sort(ord.begin(), ord.end(),
       [&](const pair<long long, long long>& a,
           const pair<long long, long long>& b) {
         return cmp(a.first, a.second, b.first, b.second);
       });
  reverse(ord.begin(), ord.end());
  long long l = 0, r = ((long long)ord.size()) - 1;
  while (r - l > 1) {
    long long mid = (l + r) / 2;
    if (check(mid)) {
      l = mid;
    } else {
      r = mid;
    }
  }
  long long ans_l, ans_r;
  if (check(r))
    ans_l = ord[r].first, ans_r = ord[r].second;
  else
    ans_l = ord[l].first, ans_r = ord[l].second;
  for (long long i = ans_l; i <= ans_r; i++) {
    cout << s[i];
  }
  cout << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(12);
  my_main();
  return 0;
}

### Prompt

Develop a solution in CPP to the problem described below:

VK just opened its second HQ in St. Petersburg! Side of its office building has a huge string s written on its side. This part of the office is supposed to be split into m meeting rooms in such way that meeting room walls are strictly between letters on the building. Obviously, meeting rooms should not be of size 0, but can be as small as one letter wide. Each meeting room will be named after the substring of s written on its side.

<image>

For each possible arrangement of m meeting rooms we ordered a test meeting room label for the meeting room with lexicographically minimal name. When delivered, those labels got sorted backward lexicographically.

What is printed on kth label of the delivery?

Input

In the first line, you are given three integer numbers n, m, k — length of string s, number of planned meeting rooms to split s into and number of the interesting label (2 ≤ n ≤ 1 000; 1 ≤ m ≤ 1 000; 1 ≤ k ≤ 10^{18}).

Second input line has string s, consisting of n lowercase english letters.

For given n, m, k there are at least k ways to split s into m substrings.

Output

Output single string – name of meeting room printed on k-th label of the delivery.

Examples

Input


4 2 1
abac


Output


aba


Input


19 5 1821
aupontrougevkoffice


Output


au

Note

In the first example, delivery consists of the labels "aba", "ab", "a".

In the second example, delivery consists of 3060 labels. The first label is "aupontrougevkof" and the last one is "a".

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (long long i = 0; i < static_cast<long long>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
using ll = long long;
const long long MAXN = 1005;
char s[MAXN];
namespace Hash {
const long long base1 = 131;
const long long base2 = 233;
const long long MOD1 = 1e9 + 7;
const long long MOD2 = 1e9 + 9;
long long p1[MAXN], p2[MAXN], h1[MAXN], h2[MAXN];
void init(char s[], long long n) {
  p1[0] = p2[0] = 1;
  h1[0] = h2[0] = 0;
  for (long long i = 1; i <= n; i++) {
    p1[i] = (p1[i - 1] * base1) % MOD1;
    p2[i] = (p2[i - 1] * base2) % MOD2;
    h1[i] = (h1[i - 1] * base1 + s[i]) % MOD1;
    h2[i] = (h2[i - 1] * base2 + s[i]) % MOD2;
  }
}
long long getHash(long long l, long long r) {
  long long H1 = ((h1[r] - h1[l - 1] * p1[r - l + 1]) % MOD1 + MOD1) % MOD1;
  long long H2 = ((h2[r] - h2[l - 1] * p2[r - l + 1]) % MOD2 + MOD2) % MOD2;
  return H1 * MOD2 + H2;
}
}  // namespace Hash
vector<pair<long long, long long>> ord;
long long n, m, rk[MAXN], lcp[MAXN][MAXN];
long long k, dp[MAXN][MAXN], dp1[MAXN][MAXN], dp2[MAXN][MAXN];
bool cmp(long long l1, long long r1, long long l2, long long r2) {
  long long len1 = r1 - l1 + 1, len2 = r2 - l2 + 1;
  bool ret;
  if (lcp[l1][l2] >= min(len1, len2)) {
    ret = len1 < len2;
  } else {
    ret = rk[l1] < rk[l2];
  }
  return ret;
};
bool check(long long first) {
  memset(dp, 0, sizeof(dp));
  vector<long long> to(n + 1);
  for (long long i = 0; i <= n; i++) to[i] = i + 1;
  for (long long i = first; i < ((long long)ord.size()); i++) {
    to[ord[i].first - 1] = max(to[ord[i].first - 1], ord[i].second + 1);
  }
  dp[0][0] = 1;
  for (long long j = 0; j <= m; j++) {
    if (j)
      for (long long i = 1; i <= n; i++) {
        dp[i][j] += dp[i - 1][j];
        if (dp[i][j] > k) dp[i][j] = k;
      }
    for (long long i = j; i <= n; i++) {
      if (to[i] <= n) {
        dp[to[i]][j + 1] += dp[i][j];
        if (dp[to[i]][j + 1] > k) {
          dp[to[i]][j + 1] = k;
        }
      }
    }
  }
  return dp[n][m] < k;
}
long long suck[MAXN];
void my_main() {
  cin >> n >> m >> k;
  cin >> (s + 1);
  Hash::init(s, n);
  for (long long i = 1; i <= n; i++) {
    for (long long j = i; j <= n; j++) {
      ord.push_back({i, j});
    }
  }
  for (long long i = 1; i <= n; i++) suck[i] = i;
  auto fuck = [&](long long first, long long second) {
    string s1, s2;
    for (long long i = first; i <= n; i++) s1 += s[i];
    for (long long i = second; i <= n; i++) s2 += s[i];
    return s1 < s2;
  };
  sort(suck + 1, suck + n + 1, fuck);
  for (long long i = 1; i <= n; i++) rk[suck[i]] = i;
  for (long long i = 1; i <= n; i++) {
    for (long long j = 1; j <= n; j++) {
      long long l = 1, r = min(n - i + 1, n - j + 1);
      while (r - l > 1) {
        long long mid = (l + r) / 2;
        if (Hash::getHash(i, i + mid - 1) == Hash::getHash(j, j + mid - 1)) {
          l = mid;
        } else {
          r = mid;
        }
      }
      if (Hash::getHash(i, i + r - 1) == Hash::getHash(j, j + r - 1)) {
        lcp[i][j] = r;
      } else if (Hash::getHash(i, i + l - 1) == Hash::getHash(j, j + l - 1)) {
        lcp[i][j] = l;
      } else {
        assert(l == 1);
        lcp[i][j] = 0;
      }
    }
  }
  sort(ord.begin(), ord.end(),
       [&](const pair<long long, long long>& a,
           const pair<long long, long long>& b) {
         return cmp(a.first, a.second, b.first, b.second);
       });
  reverse(ord.begin(), ord.end());
  long long l = 0, r = ((long long)ord.size()) - 1;
  while (r - l > 1) {
    long long mid = (l + r) / 2;
    if (check(mid)) {
      l = mid;
    } else {
      r = mid;
    }
  }
  long long ans_l, ans_r;
  if (check(r))
    ans_l = ord[r].first, ans_r = ord[r].second;
  else
    ans_l = ord[l].first, ans_r = ord[l].second;
  for (long long i = ans_l; i <= ans_r; i++) {
    cout << s[i];
  }
  cout << endl;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(12);
  my_main();
  return 0;
}

```