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.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/**
 * Created by sbabkin on 9/14/2015.
 */
public class SolverE {

    public static void main(String[] args) throws IOException {
        new SolverE().Run();
    }

    BufferedReader br;
    PrintWriter pw;
    StringTokenizer stok;

    private String nextToken() throws IOException {
        while (stok == null || !stok.hasMoreTokens()) {
            stok = new StringTokenizer(br.readLine());
        }
        return stok.nextToken();
    }

    private int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    private long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    class Trie {

        int count;
        Trie a, b;
//        Trie[] next = new Trie[2];

        public void addWord(int start) {
            Trie curNode = this;
            for (int curPos = start; curPos < len; curPos++) {
                if (str.charAt(curPos) == 'a') {
                    if (curNode.a == null) {
                        curNode.a = new Trie();
                    }
                    curNode = curNode.a;
                } else {
                    if (curNode.b == null) {
                        curNode.b = new Trie();
                    }
                    curNode = curNode.b;
                }
                if (isPal[start][curPos]) {
                    curNode.count++;
                }

            }
//            int ind = (int) str.charAt(curPos) - (int) 'a';
//            if (next[ind] == null) {
//                next[ind] = new Trie();
//            }
//            if (isPal[start][curPos]) {
//                next[ind].count++;
//            }
//            if (curPos + 1 < len) {
//                next[ind].addWord(curPos + 1, start);
//            }
        }
    }

    String str;
    int k, len;
    boolean[][] isPal;
    int[] resMas;
    //    Trie root;
    boolean found = false;
    int curNum = 0;
    int[] count;
    int[] left;
    int[] right;
    int size = 1;

    private void Run() throws IOException {
//        br = new BufferedReader(new FileReader("input.txt"));
//        pw = new PrintWriter("output.txt");
        br = new BufferedReader(new InputStreamReader(System.in));
        pw = new PrintWriter(new OutputStreamWriter(System.out));

        str = br.readLine();
        len = str.length();
        k = nextInt();
        count=new int[len*(len+1)/2 + 10];
        left=new int[len*(len+1)/2 + 10];
        right=new int[len*(len+1)/2 + 10];
        isPal = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            isPal[i][i] = true;
        }
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < i; j++) {
                isPal[i][j] = true;
            }
        }
        for (int i = 0; i < len - 1; i++) {
            if (str.charAt(i) == str.charAt(i + 1)) {
                isPal[i][i + 1] = true;
            }
        }
        for (int curLen = 2; curLen < len; curLen++) {
            for (int i = 0; i < len - curLen; i++) {
                if (((i + 2 > i + curLen - 2) || isPal[i + 2][i + curLen - 2]) && str.charAt(i) == str.charAt(i + curLen)) {
                    isPal[i][i + curLen] = true;
                }
            }
        }

        for (int i = 0; i < len; i++) {
            addWord(i);
        }
        resMas = new int[len];
        findWord(0, 0);
        pw.flush();
        pw.close();
    }

    private void addWord(int start) {
        int curInd = 0;
        for (int curPos = start; curPos < len; curPos++) {
            if (str.charAt(curPos) == 'a') {
                if (left[curInd] == 0) {
                    left[curInd] =size;
                    size++;
                }
                curInd = left[curInd];
            } else {
                if (right[curInd] == 0) {
                    right[curInd]= size;
                    size++;
                }
                curInd = right[curInd];
            }
            if (isPal[start][curPos]) {
                count[curInd]++;
            }
        }
    }

    private void findWord(int curInd, int dep) {
        curNum += count[curInd];
        if (curNum >= k && !found) {
            found = true;
            for (int i = 0; i < dep; i++) {
                if (resMas[i] == 0) {
                    pw.print('a');
                } else {
                    pw.print('b');
                }
            }
            pw.println();
            return;
        }
        if (left[curInd] > 0) {
            resMas[dep] = 0;
            findWord(left[curInd], dep + 1);
        }
        if (right[curInd] > 0) {
            resMas[dep] = 1;
            findWord(right[curInd], dep + 1);
        }

//        if (curNum >= k && !found) {
//            found = true;
//            for (int i = 0; i < dep; i++) {
//                if (resMas[i] == 0) {
//                    pw.print('a');
//                } else {
//                    pw.print('b');
//                }
//            }
//            pw.println();
//            return;
//        }
//        if (node.a != null) {
//            resMas[dep] = 0;
//            findWord(node.a, dep + 1);
//        }
//        if (node.b != null) {
//            resMas[dep] = 1;
//            findWord(node.b, dep + 1);
//        }
//        for (int i = 0; i < 2; i++) {
//            if (node.next[i] != null) {
//                resMas[dep] = i;
//                findWord(node.next[i], dep + 1);
//            }
//        }
    }

}
