K-th Substring

Sort every substring of S lexicographically and print the K-th one, or -1 if there are fewer than K substrings.

Medium7StringSortingBinary searchNo attempts yetTime limit2sMemory limit512 MB

Description

Examples3

Problem

A substring of $S$ is the string you get by cutting one contiguous block of characters out of $S$ . Two cuts at different places count as two substrings even when the text is the same, so a string of length $n$ has $\frac{n(n+1)}{2}$ substrings in total.

Sort all substrings of $S$ in lexicographic order and find the $K$ -th one.

Input

The first line contains the string $S$ . It consists of lowercase letters only, and its length is between $1$ and $100{,}000$ .

The second line contains the integer $K$ ( $1 \le K \le 100{,}000$ ).

Output

Print the substring of $S$ that comes $K$ -th in lexicographic order. If $S$ has fewer than $K$ substrings, print $-1$ .