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). 

import java.util.*;
import java.io.*;

public class E
{
   public static void main(String[] args)
   {
      PrintWriter out = new PrintWriter(System.out);
      new E(new FastScanner(), out);
      out.close();
   }

   int MAX_NODES = 13_000_000, id_ptr = 1;
   int[][] nxt;
   int[] numHalfPali, sumHalfPali;

   void bootstrap(int cur)
   {
      for (int i=0; i<2; i++)
      {
         int n = nxt[i][cur];
         if (n != -1)
         {
            bootstrap(n);
            sumHalfPali[cur] += sumHalfPali[n];
         }
      }
      sumHalfPali[cur] += numHalfPali[cur];
   }

   void add(int cur, int i, String s, int offset, boolean[] isPali)
   {
      if (i > 0 && isPali[offset+i-1])
         numHalfPali[cur]++;
      if (offset+i == s.length())
         return;
      int v = (int)(s.charAt(offset+i)-'a');
      if (nxt[v][cur] == -1)
         nxt[v][cur] = id_ptr++;
      add(nxt[v][cur], i+1, s, offset, isPali);
   }

   public E(FastScanner in, PrintWriter out)
   {
      nxt = new int[2][MAX_NODES];
      for (int[] nn : nxt) Arrays.fill(nn, -1);
      numHalfPali = new int[MAX_NODES];
      sumHalfPali = new int[MAX_NODES];

      String s = in.next();
      int K = in.nextInt()-1;
      int N = s.length();
      boolean[][] isPali = new boolean[N][N];
      for (int len=1; len<5; len++)
         for (int i=0; i+len<=N; i++)
            isPali[i][i+len-1] = s.charAt(i) == s.charAt(i+len-1);
      for (int len=5; len<=N; len++)
         for (int i=0; i+len<=N; i++)
            isPali[i][i+len-1] = s.charAt(i) == s.charAt(i+len-1) && isPali[i+2][i+len-3];

      for (int i=0; i<s.length(); i++)
         add(0, 0, s, i, isPali[i]);
      bootstrap(0);

      int cur = 0;
      StringBuilder sb = new StringBuilder();
      while (K >= 0)
      {
         if (K < numHalfPali[cur])
            break;
         K -= numHalfPali[cur];
         for (int i=0; i<2; i++) if (nxt[i][cur] != -1)
         {
            if (K < sumHalfPali[nxt[i][cur]])
            {
               sb.append((char)(i+'a'));
               cur = nxt[i][cur];
               break;
            }
            
            K -= sumHalfPali[nxt[i][cur]];
         }
      }
      out.println(sb);
   }
}


class FastScanner{
   private InputStream stream;
   private byte[] buf = new byte[1024];
   private int curChar;
   private int numChars;

   public FastScanner()
   {
      stream = System.in;
   }

   int read()
   {
      if (numChars == -1)
         throw new InputMismatchException();
      if (curChar >= numChars){
         curChar = 0;
         try{
            numChars = stream.read(buf);
         } catch (IOException e) {
            throw new InputMismatchException();
         }
         if (numChars <= 0)
            return -1;
      }
      return buf[curChar++];
   }

   boolean isSpaceChar(int c)
   {
      return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1;
   }
   
   boolean isEndline(int c)
   {
      return c=='\n'||c=='\r'||c==-1;
   }

   int nextInt()
   {
      return Integer.parseInt(next());
   }
   
   long nextLong()
   {
      return Long.parseLong(next());
   }

   double nextDouble()
   {
      return Double.parseDouble(next());
   }

   String next(){
      int c = read();
      while (isSpaceChar(c))
         c = read();
      StringBuilder res = new StringBuilder();
      do{
         res.appendCodePoint(c);
         c = read();
      }while(!isSpaceChar(c));
      return res.toString();
   }
   
   String nextLine(){
      int c = read();
      while (isEndline(c))
         c = read();
      StringBuilder res = new StringBuilder();
      do{
         res.appendCodePoint(c);
         c = read();
      }while(!isEndline(c));
      return res.toString();
   }
}
