Common Substring#4659
Given two strings and , along with an integer , identify the set of all non-empty substrings that are common to both and .
Your task is to determine the -th smallest string in lexicographical order from this set.
The input consists of three lines. The first line contains the string , and the second line contains the string , where 1 \leq |s|, |t| \leq 10^5. The third line contains the integer with 1 \leq k \leq 10^{18}.
Both strings are composed of lowercase Latin letters.
Output the -th lexicographically smallest common substring on the first line. If such a substring does not exist, output .
Example 1