Common Substring

Given two strings (s) and (t), along with an integer (k), identify the set of all non-empty substrings that are common to both (s) and (t).

Your task is to determine the (k)-th smallest string in lexicographical order from this set.

Input

The input consists of three lines. The first line contains the string (s), and the second line contains the string (t), where (1 $\le$ |s|, |t| $\le$ 10^5). The third line contains the integer (k) with (1 $\le$ k $\le$ 10^18).

Both strings are composed of lowercase Latin letters.

Output

Output the (k)-th lexicographically smallest common substring on the first line. If such a substring does not exist, output (-1).

Examples