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). 
/**
 * Created by Aminul on 8/29/2018.
 */

import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class CF557E { //AC
    public static void main(String[] args)throws Exception {
        FastReader in = new FastReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        String str = in.next();
        s = str.toCharArray();
        int k = in.nextInt();
        int n = s.length;
        vis = new boolean[n][n];
        dp = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++){
                dp[i][j] = isHalfPalindrome(i, j);
            }
        }

        TrieArray trie = new TrieArray((n*(n+1))/2+10, 2);

        for(int i = 0; i < n; i++){
            trie.add(s, i);
        }

        StringBuilder sb = new StringBuilder();
        trie.getKth(trie.ROOT, k, sb);
        pw.println(sb.toString());

        pw.close();
    }
    static char[] s;
    static boolean dp[][], vis[][];
    static boolean isHalfPalindrome(int i, int j) {
        if (i >= j) return true;
        if (vis[i][j]) return dp[i][j];
        vis[i][j] = true;
        return dp[i][j] = (s[i] == s[j] && isHalfPalindrome(i + 2, j - 2));
    }

    static class TrieArray{
        int tree[][];
        int cnt[], total[];
        int ROOT;
        int id = 1;
        int N, alphabet;

        TrieArray(int N, int a){
            this.N = N;
            alphabet = a;
            tree = new int[2][N];
            cnt = new int[N];
            total = new int[N];
            id = ROOT = 1;
            id++;
        }


        void add(char s[], int start){
            add(ROOT, s, start, start);
        }

        int add(int root, char[] str, int i, int start) {
            if(i >= str.length) return 0;
            int ret = 0;
            if(tree[str[i]-'a'][root] == 0) {
                tree[str[i]-'a'][root] = id++;
            }
            root = tree[str[i]-'a'][root];
            if(dp[start][i]){
                ret++;
                cnt[root]++;
            }
            ret += add(root, str, i+1, start);
            total[root] += ret;
            return ret;
        }

        void getKth(int u, int k, StringBuilder sb){
            if(k <= 0) return;
            if(k <= total[tree[0][u]]){
                sb.append('a');
                getKth(tree[0][u], k-cnt[tree[0][u]], sb);
            }
            else{
                sb.append('b');
                getKth(tree[1][u], k - total[tree[0][u]]-cnt[tree[1][u]], sb);
            }
        }
    }

    static void debug(Object...obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class FastReader {
        InputStream is;
        private byte[] inbuf = new byte[1024];
        private int lenbuf = 0, ptrbuf = 0;
        static final int ints[] = new int[128];

        public FastReader(InputStream is){
            for(int i='0';i<='9';i++) ints[i]=i-'0';
            this.is = is;
        }

        public int readByte(){
            if(lenbuf == -1)throw new InputMismatchException();
            if(ptrbuf >= lenbuf){
                ptrbuf = 0;
                try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
                if(lenbuf <= 0)return -1;
            }
            return inbuf[ptrbuf++];
        }

        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }
        public int skip() {
            int b;
            while((b = readByte()) != -1 && isSpaceChar(b));
            return b;
        }

        public String next(){
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public int nextInt(){
            int num = 0, b;
            boolean minus = false;
            while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
            if(b == '-'){
                minus = true;
                b = readByte();
            }

            while(true){
                if(b >= '0' && b <= '9'){
                    num = (num<<3) + (num<<1) + ints[b];
                }else{
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public long nextLong() {
            long num = 0;
            int b;
            boolean minus = false;
            while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
            if(b == '-'){
                minus = true;
                b = readByte();
            }

            while(true){
                if(b >= '0' && b <= '9'){
                    num = (num<<3) + (num<<1) + ints[b];
                }else{
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }
       /* public char nextChar() {
            return (char)skip();
        }*/

        public char[] next(int n){
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while(p < n && !(isSpaceChar(b))){
                buf[p++] = (char)b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }

        /*private char buff[] = new char[1005];
        public char[] nextCharArray(){
            int b = skip(), p = 0;
            while(!(isSpaceChar(b))){
                buff[p++] = (char)b;
                b = readByte();
            }
            return Arrays.copyOf(buff, p);
        }*/
    }

}