Dans votre usine, vous fabriquez deux types de papier coloré, l'un rouge et l'autre bleu. Chaque papier rouge porte une chaîne $S$ : il est composé de $|S|$ carrés unitaires alignés, et $S_i$ est écrit sur le $i$-ème carré en partant de la gauche. Chaque papier bleu porte une chaîne $T$ : il est composé de $|T|$ carrés unitaires alignés, et $T_i$ est écrit sur le $i$-ème carré en partant de la gauche.
Vous prévoyez de fabriquer un nouveau type de papier appelé papier bicolore à partir de papier rouge et de papier bleu. Pour ce faire, vous coupez un morceau de papier rouge pour ne garder qu'une partie continue de longueur entière positive, puis vous faites de même avec un morceau de papier bleu. Ensuite, vous collez la fin du morceau rouge au début du morceau bleu.
Par exemple, supposons que $S$ soit abcde et $T$ soit fghij. Vous pouvez fabriquer un papier bicolore avec la chaîne bcdfg ou abcij écrite dessus. Cependant, vous ne pouvez pas fabriquer un papier bicolore avec la chaîne acdghij ou fghij écrite dessus. (Ici, la chaîne soulignée désigne un morceau rouge, et le reste désigne un morceau bleu.) Deux morceaux de papier bicolore sont considérés comme identiques s'ils portent la même chaîne rouge et la même chaîne bleue.
Parmi tous les différents morceaux de papier bicolore pouvant être fabriqués, vous souhaitez connaître celui dont la chaîne écrite dessus est la $K$-ième plus petite dans l'ordre lexicographique. Notez qu'il peut exister des papiers portant les mêmes chaînes, mais avec des longueurs de papier rouge différentes : dans ce cas, vous pouvez les ordonner arbitrairement.
Entrée
La première ligne contient la chaîne $S$. La deuxième ligne contient la chaîne $T$. La troisième ligne contient l'entier $K$.
- $1 \le |S| \le 75\,000$
- $1 \le |T| \le 75\,000$
- $S$ et $T$ sont constituées de lettres minuscules anglaises
- $1 \le K \le 8 \cdot 10^{18}$
Sortie
Si le nombre total de papiers bicolores possibles est strictement inférieur à $K$, affichez $-1$. Sinon, affichez la $K$-ième plus petite chaîne, dans l'ordre lexicographique, parmi tous les papiers bicolores possibles pouvant être fabriqués.
Exemples
Entrée 1
tww wtw 21
Sortie 1
wwtw