kthsubstring

Problem Statement

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 = x1x2...xn and Y = y1y2...ym be two distinct strings. X is lexicographically larger than Y if and only if Y is a prefix of X or xj > yj where j is the smallest integer such that xj ≠ yj.

Constraints

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

Partial Score

  • 67 points will be awarded as a partial score for passing the test set satisfying |s| 50.

Input

Input is given from Standard Input in the following format:

s
K

Output

Print the K-th lexicographically smallest substring of K.

Sample Input 1

aba
4

Sample Output 1

b

s has five substrings: a, b, ab, ba and aba. Among them, we should print the fourth smallest one, b. Note that we do not count a twice.

Sample Input 2

atcoderandatcodeer
5

Sample Output 2

andat

Sample Input 3

z
1

Sample Output 3

z

Submitting to 'kthsubstring'


You're not logged in! Click here to login


Submitting to 'kthsubstring'


You're not logged in! Click here to login


Submitting .cpp to 'kthsubstring'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 2 Seconds
Memory Limit: 256MB
No. of ACs: 10
Your best score: 0
Source: ARC 097

Subtask Score
1 67
2 33
3 0