Double-Colored Papers

In your factory, you are making two kinds of colored paper, one colored red, and the other colored blue.

Each red-colored paper has a string $S$ written on it: it is made of $|S|$ unit squares in a row, and $S\_i$ is written on the $i$th square from the left.

Each blue-colored paper has a string $T$ written on it: it is made of $|T|$ unit squares in a row, and $T\_i$ is written on the $i$th square from the left.

You plan to make a new kind of paper called double-colored paper out of red and blue paper. To do so, you will cut down a piece of red paper to only leave the continuous part with a positive integer length, and again with blue paper. Then, you will glue the ending part of the red paper to the starting part of the blue paper.

For example, suppose $S$ is abcde and $T$ is fghij. You can make a double-colored paper with string bcdfg or abcij written on it. However, you cannot make a double-colored paper with string acdghij or fghij written on it. (Here the underlined string denotes a part of the red paper, and the rest denotes a part of the blue paper.)

Among all possible double-colored papers that can be made, you want to know the one with the lexicographically $K$-th smallest string written on it. Note that there may be papers with the same strings written on them, but with different lengths of red paper: in this case, you may order them arbitrarily.

The first line contains string $S$.

The second line contains string $T$.

The third line contains integer $K$.

If the total number of possible double-colored papers is strictly less than $K$, output $-1$.

Otherwise, output the lexicographically $K$-th smallest string of all possible double-colored papers that can be made.

• $1\le |S|\le 75\\, 000$
• $1\le |T|\le 75\\, 000$
• $S$ and $T$ consists of lowercase alphabets.
• $1\le K\le 8\times 10^{18}$