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.InputStream;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    private class Node {
        int sum, cnt;
        Node a, b;

        public Node(int sum, int cnt, Node a, Node b) {
            this.sum = sum;
            this.cnt = cnt;
            this.a = a;
            this.b = b;
        }
    }

    private String s;
    private int n, id;
    private boolean[][] dp1, dp2;
    private int[] max;
    private Node root;
    private StringBuffer res = new StringBuffer();

    private void DFS(Node root) {
        if (root == null) return;
        DFS(root.a);
        DFS(root.b);
        if (root.a != null) root.sum += root.a.sum;
        if (root.b != null) root.sum += root.b.sum;
        root.sum += root.cnt;
    }

    private void Print(Node root) {
        if (root == null) return;
        if (id <= 0) return;
        if (root.a != null && id <= root.a.sum) {
            res.append('a');
            id -= root.a.cnt;
            Print(root.a);
            return;
        }
        if (root.a != null) id -= root.a.sum;
        if (root.b != null && id > 0) {
            res.append('b');
            id -= root.b.cnt;
            Print(root.b);
        }
    }

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        s = in.next();
        n = s.length();

        dp1 = new boolean[n][n];
        dp2 = new boolean[n][n];

        for (int i = 0; i < n; ++i) {
            dp1[i][i] = true;
            dp2[i][i] = true;
            for (int j = 0; j < i; ++j) {
                dp1[i][j] = true;
                dp2[i][j] = true;
            }
        }

        for (int len = 2; len <= n; ++len)
            for (int i = 0; i <= n - len; ++i) {
                int j = i + len - 1;
                dp1[i][j] = (s.charAt(i) == s.charAt(j) && dp2[i + 1][j - 1]);
                dp2[i][j] = dp1[i + 1][j - 1];
            }

        id = in.nextInt();

        max = new int[n];
        for (int i = 0; i < n; ++i)
            for (int j = i; j < n; ++j)
                if (dp1[i][j]) max[i] = j;

        root = new Node(0, 0, null, null);
        for (int i = 0; i < n; ++i) {
            Node p = root;
            for (int j = i; j <= max[i]; ++j) {
                if (s.charAt(j) == 'a') {
                    if (p.a == null) p.a = new Node(0, (dp1[i][j] ? 1 : 0), null, null);
                    else if (dp1[i][j]) ++p.a.cnt;
                    p = p.a;
                } else {
                    if (p.b == null) p.b = new Node(0, (dp1[i][j] ? 1 : 0), null, null);
                    else if (dp1[i][j]) ++p.b.cnt;
                    p = p.b;
                }
            }
        }

        DFS(root);
        Print(root);

        out.println(res);
    }
}

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream));
        tokenizer = null;
    }

    public String next() {
        try {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        } catch (Exception e) {
            throw new UnknownError(e.getMessage());
        }
    }

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

}

