Tomorrow Ann takes the hardest exam of programming where she should get an excellent mark. 

On the last theoretical class the teacher introduced the notion of a half-palindrome. 

String t is a half-palindrome, if for all the odd positions i (<image>) the following condition is held: ti = t|t| - i + 1, where |t| is the length of string t if positions are indexed from 1. For example, strings "abaa", "a", "bb", "abbbaa" are half-palindromes and strings "ab", "bba" and "aaabaa" are not.

Ann knows that on the exam she will get string s, consisting only of letters a and b, and number k. To get an excellent mark she has to find the k-th in the lexicographical order string among all substrings of s that are half-palyndromes. Note that each substring in this order is considered as many times as many times it occurs in s.

The teachers guarantees that the given number k doesn't exceed the number of substrings of the given string that are half-palindromes.

Can you cope with this problem?

Input

The first line of the input contains string s (1 ≤ |s| ≤ 5000), consisting only of characters 'a' and 'b', where |s| is the length of string s.

The second line contains a positive integer k — the lexicographical number of the requested string among all the half-palindrome substrings of the given string s. The strings are numbered starting from one. 

It is guaranteed that number k doesn't exceed the number of substrings of the given string that are half-palindromes.

Output

Print a substring of the given string that is the k-th in the lexicographical order of all substrings of the given string that are half-palindromes.

Examples

Input

abbabaab
7


Output

abaa


Input

aaaaa
10


Output

aaa


Input

bbaabb
13


Output

bbaabb

Note

By definition, string a = a1a2... an is lexicographically less than string b = b1b2... bm, if either a is a prefix of b and doesn't coincide with b, or there exists such i, that a1 = b1, a2 = b2, ... ai - 1 = bi - 1, ai < bi.

In the first sample half-palindrome substrings are the following strings — a, a, a, a, aa, aba, abaa, abba, abbabaa, b, b, b, b, baab, bab, bb, bbab, bbabaab (the list is given in the lexicographical order). 
#include <bits/stdc++.h>
#pragma GCC optimize(3)
#pragma warning(disable : 4996)
template <typename T>
T min(T x, T y) {
  return x < y ? x : y;
}
template <typename T>
T max(T x, T y) {
  return x > y ? x : y;
};
const long long MAXN = 15005;
const int INF = 1000000000;
void print(int *a, int n) {
  for (int i = 0; i < n; i++) printf("%d%c", a[i], i == n - 1 ? '\n' : ' ');
}
void print(std::pair<int, int> p) { printf("%d %d\n", p.first, p.second); }
bool cmp(char *s1, char *s2) {
  while (s1[0] == s2[0] && s1[0] && s2[0]) s1++, s2++;
  return s1[0] < s2[0];
}
struct pair {
  int id;
  int fir;
  int sec;
  pair(int ID = 0, int F = 0, int S = 0) {
    id = ID;
    fir = F;
    sec = S;
  }
};
char bak[MAXN];
int LEN, f[MAXN], rank[MAXN], lcp[25][MAXN];
pair tmp1[MAXN], tmp2[MAXN];
void SA(char *str) {
  static int cnt[MAXN];
  LEN = strlen(str);
  memcpy(bak, str, sizeof(char) * LEN);
  for (int i = 0; i < LEN; i++) rank[i] = str[i];
  for (int i = 0; i < 25; i++) {
    for (int j = 0; j < LEN; j++)
      tmp1[j] = pair(j, rank[j], rank[min(LEN, j + (1 << i))]);
    memset(cnt, 0, sizeof(cnt));
    for (int j = 0; j < LEN; j++) cnt[tmp1[j].sec]++;
    for (int j = 1; j < MAXN; j++) cnt[j] += cnt[j - 1];
    for (int j = LEN - 1; j >= 0; j--) tmp2[--cnt[tmp1[j].sec]] = tmp1[j];
    memset(cnt, 0, sizeof(cnt));
    for (int j = 0; j < LEN; j++) cnt[tmp2[j].fir]++;
    for (int j = 1; j < MAXN; j++) cnt[j] += cnt[j - 1];
    for (int j = LEN - 1; j >= 0; j--) tmp1[--cnt[tmp2[j].fir]] = tmp2[j];
    int cur = 1;
    bool flag = true;
    for (int j = 0; j < LEN; j++) {
      if (j &&
          (tmp1[j].fir != tmp1[j - 1].fir || tmp1[j].sec != tmp1[j - 1].sec))
        cur++;
      else if (j)
        flag = false;
      rank[tmp1[j].id] = cur;
    }
    if (flag) {
      for (int i = 0; i < LEN; i++) rank[i]--;
      break;
    }
  }
  for (int i = 0; i < LEN; i++) f[rank[i]] = i;
  for (int i = 0; i < LEN; i++) {
    if (rank[i] == 0) continue;
    int t = max(i ? lcp[0][rank[i - 1]] - 1 : 0, 0);
    while (str[i + t] == str[f[rank[i] - 1] + t]) t++;
    lcp[0][rank[i]] = t;
  }
  for (int i = 1; i < 25; i++)
    for (int j = 0; j < LEN; j++)
      lcp[i][j] = min(lcp[i - 1][j], lcp[i - 1][min(j + (1 << (i - 1)), LEN)]);
}
int query(int x, int y) {
  if (x == y) return LEN - f[x];
  if (x > y) std::swap(x, y);
  x++;
  y++;
  int len = y - x;
  int t = 0;
  while (1 << t <= len) t++;
  t--;
  return min(lcp[t][x], lcp[t][y - (1 << t)]);
}
int find(char *s) {
  int l = -1, r = LEN;
  while (r - l > 1) {
    int mid = (l + r) / 2;
    if (cmp(bak + f[mid], s))
      l = mid;
    else
      r = mid;
  }
  for (int i = 0; s[i]; i++)
    if (bak[f[r] + i] != s[i]) return LEN;
  return f[r];
}
int N, K;
char str[MAXN];
std::bitset<5005> b[5005];
int T[5005][5005];
int query(int x1, int x2, int y1, int y2) {
  int ans = T[x2][y2];
  if (x1) ans -= T[x1 - 1][y2];
  if (y1) ans -= T[x2][y1 - 1];
  if (x1 && y1) ans += T[x1 - 1][y1 - 1];
  return ans;
}
void init() {
  scanf("%s", str);
  scanf("%d", &K);
  N = strlen(str);
  for (int i = 0; i < N; i++) {
    for (int j = 0; j <= i && i + j < N && str[i - j] == str[i + j]; j += 2)
      b[i - j][i + j] = true;
    for (int j = 1; j <= i && i + j < N && str[i - j] == str[i + j]; j += 2)
      b[i - j][i + j] = true;
    for (int j = 0; j <= i && i + 1 + j < N && str[i - j] == str[i + 1 + j];
         j += 2)
      b[i - j][i + 1 + j] = true;
    for (int j = 1; j <= i && i + 1 + j < N && str[i - j] == str[i + 1 + j];
         j += 2)
      b[i - j][i + 1 + j] = true;
  }
  SA(str);
  for (int i = 0; i < LEN; i++) {
    int pos = f[i];
    for (int j = pos; j < LEN; j++)
      if (b[pos][j]) T[i][j - pos + 1]++;
  }
  for (int i = 0; i < 5005; i++)
    for (int j = 0; j < 5005; j++)
      T[i][j] += (i ? T[i - 1][j] : 0) + (j ? T[i][j - 1] : 0) -
                 (i && j ? T[i - 1][j - 1] : 0);
}
std::pair<int, int> get_range(char *s) {
  int len = strlen(s);
  int pos = find(s);
  if (pos == LEN) return std::make_pair(LEN, LEN);
  int fp = rank[pos];
  int L, R;
  int l = -1, r = fp;
  while (r - l > 1) {
    int mid = (l + r) / 2;
    if (query(mid, fp) >= len)
      r = mid;
    else
      l = mid;
  }
  L = r;
  l = fp, r = LEN;
  while (r - l > 1) {
    int mid = (l + r) / 2;
    if (query(mid, fp) >= len)
      l = mid;
    else
      r = mid;
  }
  R = l;
  return std::make_pair(L, R);
}
void solve(int K) {
  static char ans[MAXN] = {};
  for (int i = 0; i < LEN; i++) {
    for (int j = 0; j < 26; j++) {
      ans[i] = 'a' + j;
      std::pair<int, int> r = get_range(ans);
      if (r.first == LEN) continue;
      int tmp = query(r.first, r.second, i + 1, i + 1);
      if (tmp >= K) {
        printf("%s", ans);
        return;
      }
      int t = query(r.first, r.second, i + 1, 5000);
      if (t >= K) {
        K -= tmp;
        break;
      } else
        K -= t;
    }
  }
}
int test(char *s) {
  std::pair<int, int> r = get_range(s);
  return query(r.first, r.second, strlen(s), 5000);
}
int main() {
  init();
  solve(K);
  return 0;
}
