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.Arrays;
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
 * @author Artem Gilmudinov
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		Reader in = new Reader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    int[] trie;
    int[] cnt;
    int curCnt = 0;
    int k;
    boolean found = false;
    int res = 0;
    public void solve(int testNumber, Reader in, PrintWriter out) {
        String s = in.rl();
        int n = s.length();
        k = in.ni();
        int[] v = new int[n];
        for(int i = 0; i < n; i++) {
            v[i] = s.charAt(i) - 'a';
        }
        int[][] node = new int[n][n];
        trie = new int[(n * (n - 1)) + 5];
        cnt = new int[(n * (n - 1)) + 5];
        Arrays.fill(trie, -1);
        int curNode = 0;
        int lastFree = 2;
        for(int i = 0; i < n; i++) {
            curNode = 0;
            for(int j = i; j < n; j++) {
                if(trie[curNode + v[j]] == -1) {
                    trie[curNode + v[j]] = lastFree;
                    lastFree += 2;
                }
                node[i][j] = curNode + v[j];
                curNode = trie[curNode + v[j]];
            }
        }
        boolean[][] odd = new boolean[n][2];
        boolean[][] oddPrev = new boolean[n][2];
        boolean[][] even = new boolean[n][2];
        boolean[][] evenPrev = new boolean[n][2];
        for(int i = 0; i < n; i++) {
            oddPrev[i][0] = oddPrev[i][1] = true;
            cnt[node[i][i]]++;
        }
        for(int i = 0; i < n - 1; i++) {
            evenPrev[i][0] = (s.charAt(i) == s.charAt(i + 1));
            if(evenPrev[i][0]) {
                cnt[node[i][i + 1]]++;
            }
            evenPrev[i][1] = true;
        }
        for(int i = 3; i <= n; i++) {
            for(int j = 0; j < n; j++) {
                odd[j][0] = odd[j][1] = false;
                even[j][0] = even[j][1] = false;
            }
            if(i % 2 != 0) {
                for(int j = 0; j <= n - i; j++) {
                    odd[j][0] = s.charAt(j) == s.charAt(j + i - 1) && oddPrev[j + 1][1];
                    odd[j][1] = oddPrev[j + 1][0];
                }
            } else {
                for(int j = 0; j <= n - i; j++) {
                    even[j][0] = s.charAt(j) == s.charAt(j + i -1) && evenPrev[j + 1][1];
                    even[j][1] = evenPrev[j + 1][0];
                }
            }
            for(int j = 0; j <= n - i; j++) {
                if(even[j][0]) {
                    cnt[node[j][j + i - 1]]++;
                }
                if(odd[j][0]) {
                    cnt[node[j][j + i - 1]]++;
                }
            }
            for(int j = 0; j < n; j++) {
                if(i % 2 == 0) {
                    evenPrev[j][0] = even[j][0];
                    evenPrev[j][1] = even[j][1];
                } else {
                    oddPrev[j][0] = odd[j][0];
                    oddPrev[j][1] = odd[j][1];
                }
            }
        }
        dfs(0);
        for(int i = 0; i < n; i++) {
            for(int j = i; j < n; j++) {
                if(node[i][j] == res) {
                    for(int z = i; z <= j; z++) {
                        out.print(s.charAt(z));
                    }
                    return;
                }
            }
        }


    }

    public void dfs(int node) {
        for(int i = 0; i < 2; i++) {
            if (found) {
                return;
            }
            if (trie[node + i] != -1) {
                if (curCnt + cnt[node + i] >= k) {
                    found = true;
                    res = node + i;
                    return;
                } else {
                    curCnt += cnt[node + i];
                    dfs(trie[node + i]);
                }
            }
        }
    }
}

class Reader {
    private BufferedReader in;
    private StringTokenizer st = new StringTokenizer("");
    private String delim = " ";

    public Reader(InputStream in) {
        this.in = new BufferedReader(new InputStreamReader(in));
    }

    public String next() {
        if (!st.hasMoreTokens()) {
            st = new StringTokenizer(rl());
        }
        return st.nextToken(delim);
    }

    public String rl() {
        try {
            return in.readLine();
        } catch(IOException e) {
            throw new RuntimeException(e);
        }
    }

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

}

