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>
using namespace std;
const int MAXN = 5e3 + 5;
char s[MAXN];
char good[MAXN][MAXN];
int c[MAXN], cn[MAXN];
int p[MAXN], pn[MAXN];
int cnt[MAXN];
int lcp[MAXN];
int dp[MAXN][MAXN];
int pos[MAXN];
void build_suff(int n) {
  for (int i = 0; i < n; i++) {
    s[i]++;
  }
  s[n] = 'a';
  n++;
  for (int i = 0; i < n; i++) {
    cnt[s[i] - 'a']++;
  }
  cnt[1] += cnt[0];
  cnt[2] += cnt[1];
  for (int i = n - 1; i >= 0; i--) {
    p[--cnt[s[i] - 'a']] = i;
  }
  int cl = 0;
  c[p[0]] = 0;
  for (int i = 1; i < n; i++) {
    if (s[p[i]] != s[p[i - 1]]) cl++;
    c[p[i]] = cl;
  }
  for (int len = 1; len < n; len <<= 1) {
    for (int i = 0; i < n; i++) {
      cnt[i] = 0;
    }
    for (int i = 0; i < n; i++) {
      pn[i] = p[i] - len;
      if (pn[i] < 0) pn[i] += n;
    }
    for (int i = 0; i < n; i++) {
      cnt[c[pn[i]]]++;
    }
    for (int i = 1; i < n; i++) {
      cnt[i] += cnt[i - 1];
    }
    for (int i = n - 1; i >= 0; i--) {
      p[--cnt[c[pn[i]]]] = pn[i];
    }
    cl = 0;
    cn[p[0]] = 0;
    for (int i = 1; i < n; i++) {
      int m1 = p[i] + len;
      if (m1 >= n) m1 -= n;
      int m2 = p[i - 1] + len;
      if (m2 >= n) m2 -= n;
      if (c[p[i]] != c[p[i - 1]] || c[m1] != c[m2]) cl++;
      cn[p[i]] = cl;
    }
    for (int i = 0; i < n; i++) {
      c[i] = cn[i];
    }
  }
  for (int i = 0; i < n; i++) {
    s[i]--;
  }
  n--;
  for (int i = 0; i < n; i++) {
    p[i] = p[i + 1];
  }
}
void out(int n) {
  for (int i = 0; i < n; i++) {
    int l = p[i];
    for (int j = l; j < n; j++)
      if (0) cout << s[j];
    if (0) cout << endl;
  }
  for (int i = 0; i < n - 1; i++) {
    if (0) cout << lcp[i] << " ";
  }
  if (0) cout << endl;
}
void out2(int n) {
  for (int i = 0; i < n; i++) {
    if (0) cout << "#" << i << " " << lcp[i] << endl;
    for (int j = 1; j <= lcp[i]; j++) {
      if (0) cout << j << " " << dp[i][j] << endl;
    }
  }
}
void solve() {
  long long k;
  cin >> s >> k;
  int n = strlen(s);
  for (int i = 0; i < n; i++) {
    int l = i, r = i;
    for (; l >= 0 && r < n && s[l] == s[r]; l -= 2, r += 2) {
      good[l][r] = 1;
    }
  }
  for (int i = 0; i < n - 1; i++) {
    int l = i, r = i + 1;
    for (; l >= 0 && r < n && s[l] == s[r]; l -= 2, r += 2) {
      good[l][r] = 1;
    }
  }
  for (int i = 0; i < n - 1; i++) {
    int l = i - 1, r = i + 1;
    for (; l >= 0 && r < n && s[l] == s[r]; l -= 2, r += 2) {
      good[l][r] = 1;
    }
  }
  for (int i = 0; i < n - 2; i++) {
    int l = i - 1, r = i + 2;
    for (; l >= 0 && r < n && s[l] == s[r]; l -= 2, r += 2) {
      good[l][r] = 1;
    }
  }
  build_suff(n);
  for (int i = 0; i < n - 1; i++) {
    int l = p[i];
    int r = p[i + 1];
    int cur = 0;
    for (; l < n && r < n && s[l] == s[r]; l++, r++) {
      cur++;
    }
    lcp[i] = cur;
  }
  out(n);
  for (int i = 0; i < n; i++) {
    int l = p[i];
    for (int j = n - l; j >= 1; j--) {
      dp[i][j] = 1;
    }
  }
  for (int i = n - 2; i >= 0; i--) {
    int len = lcp[i];
    for (int j = 1; j <= len; j++) {
      dp[i][j] += dp[i + 1][j];
    }
  }
  out2(n);
  for (int i = 1; i <= n; i++) {
    pos[i] = 0;
  }
  for (int i = 0; i < n; i++) {
    int l = p[i];
    int last = 0;
    for (int j = l + last; j < n; j++) {
      if (good[l][j]) {
        if (i < pos[j - l + 1]) continue;
        if (dp[i][j - l + 1] >= k) {
          string ans = "";
          for (int h = l; h <= j; h++) {
            ans += s[h];
          }
          cout << ans;
          return;
        }
        k -= dp[i][j - l + 1];
        pos[j - l + 1] = max(pos[j - l + 1], i + dp[i][j - l + 1]);
      }
    }
  }
}
int main() {
  int t = 1;
  while (t--) {
    solve();
  }
  return 0;
}
