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.Random;
import java.util.StringTokenizer;

public class ProblemE {
    public static void main(String[] args) {
        int testMode = 0;
        String testInput = "a\n" +
                "1";
        /*-------------------------------------------------------------------------------------------------------*/
        FastReader in = new FastReader(testMode == 0 ? System.in : new ByteArrayInputStream(testInput.getBytes()));
        PrintWriter out = new PrintWriter(System.out);
        new ProblemSolver().solve(in, out);
        out.close();
    }
}

class ProblemSolver {
    int K;
    String res = "";
    int[][] nodes = new int[3][];

    void find(int idx) {
        K -= nodes[2][idx];
        if (K > 0) {
            for (int i = 0; i < 2; i++) {
                if (nodes[i][idx] == 0) continue;
                find(nodes[i][idx]);
                if (K <= 0) {
                    res = (i == 0 ? 'a' : 'b') + res;
                    return;
                }
            }
        }
    }

    void solve(FastReader in, PrintWriter out) {
        char[] s = in.nextToken().toCharArray();
        int n = s.length;
        K = in.nextInt();

        boolean[][] p = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            //out.println(i);
            p[i][i] = true;
            for (int k = 2; i - k >= 0 && i + k < n; k += 2) {
                if (s[i - k] != s[i + k]) break;
                p[i - k][i + k] = true;
            }
            for (int k = 1; i - k >= 0 && i + k < n; k += 2) {
                if (s[i - k] != s[i + k]) break;
                p[i - k][i + k] = true;
            }
            if (i + 1 < n) {
                if (s[i] == s[i + 1]) {
                    p[i][i + 1] = true;
                    for (int k = 2; i - k >= 0 && i + k + 1 < n; k += 2) {
                        if (s[i - k] != s[i + k + 1]) break;
                        p[i - k][i + k + 1] = true;
                    }
                }
                for (int k = 2; i - k + 1 >= 0 && i + k < n; k += 2) {
                    if (s[i - k + 1] != s[i + k]) break;
                    p[i - k + 1][i + k] = true;
                }
            }
        }

        for (int i = 0; i < 3; i++) nodes[i] = new int[n * (n + 1)];

        int next_free = 1;
        for (int i = 0; i < n; i++) {
            int idx = 0;
            for (int k = 0; i + k < n; k++) {
                int next_idx = nodes[s[i + k] - 'a'][idx];
                if (next_idx == 0) {
                    next_idx = next_free++;
                    nodes[s[i + k] - 'a'][idx] = next_idx;
                }
                if (p[i][i + k]) nodes[2][next_idx]++;
                idx = next_idx;
            }
        }

        find(0);
        out.println(res);
    }
}


class Node {
    int cnt;
    Node[] kids = new Node[2];
}


class FastReader extends BufferedReader {
    private StringTokenizer st;

    public FastReader(InputStream is) {
        super(new InputStreamReader(is));
    }

    public String nextToken() {
        try {
            while (st == null || !st.hasMoreElements()) {
                st = new StringTokenizer(readLine());
            }
            return st.nextToken();
        } catch (IOException e) {
            return null;
        }
    }

    public int nextInt() {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() {
        return Long.parseLong(nextToken());
    }

    public int[] nextArrayInt(int size) {
        int[] ret = new int[size];
        for (int i = 0; i < size; i++) {
            ret[i] = nextInt();
        }
        return ret;
    }
}