You are given a string s. Among the different substrings of s, print the K-th lexicographically smallest one.

A substring of s is a string obtained by taking out a non-empty contiguous part in s. For example, if s = `ababc`, `a`, `bab` and `ababc` are substrings of s, while `ac`, `z` and an empty string are not. Also, we say that substrings are different when they are different as strings.

Let X = x_{1}x_{2}...x_{n} and Y = y_{1}y_{2}...y_{m} be two distinct strings. X is lexicographically larger than Y if and only if Y is a prefix of X or x_{j} > y_{j} where j is the smallest integer such that x_{j} \neq y_{j}.

Constraints

* 1 ≤ |s| ≤ 5000
* s consists of lowercase English letters.
* 1 ≤ K ≤ 5
* s has at least K different substrings.

Input

Input is given from Standard Input in the following format:


s
K


Output

Print the K-th lexicographically smallest substring of K.

Examples

Input

aba
4


Output

b


Input

atcoderandatcodeer
5


Output

andat


Input

z
1


Output

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

public class Main {
	
	public static void main(String... args) {
		System.out.println(findSubstring(scanString(), scanInt()));
	}
	
	private static String findSubstring(String s, int K) {
		Dict dict = new Dict(K);
		String last = "";
		for (int i = 0; i < s.length(); ++i) {
			if (!last.isEmpty() && last.charAt(0) < s.charAt(i)) {
				continue;
			}
			int jj = Math.min(s.length(), i + K);
			for (int j = i + 1; j <= jj; ++j) {
				dict.append(s.substring(i, j));
			}
			last = dict.last();
		}
		return dict.last();
	}

	private static class Dict {
		private int K;
		
		private final ArrayList<String> dict;
		
		private Dict(int K) {
			this.K = K;
			this.dict = new ArrayList<>(K + 1);
		}
		
		private boolean hasLast() {
			return K <= dict.size();
		}
		
		private String last() {
			return hasLast() ? dict.get(K - 1) : "";
		}
		
		private boolean append(String ss) {
			if (dict.isEmpty()) {
				dict.add(ss);
				return true;
			}
			
			int p = Integer.MAX_VALUE;
			for (int i = dict.size() - 1; 0 <= i; --i) {
				String s = dict.get(i);
				int r = ss.compareTo(s);
				if (r < 0) {
					p = i;
				} else {
					if (r == 0) {
						p = -1;
					}
					break;
				}
			}
			if (dict.size() < K) {
				if (p < 0 || dict.size() <= p) {
					dict.add(ss);
				} else {
					dict.add(p, ss);
				}
			} else {
				if (p < 0 || K <= p) {
					return false;
				}
				dict.add(p, ss);
			}
			if (K < dict.size()) {
				String e = dict.remove(K);
			}
			return true;
		}
	}
	
	private static final Scanner SC = new Scanner(System.in);

	private static int scanInt() {
		return SC.nextInt();
	}

	private static  String scanString() {
		return SC.next();
	}
}
