W twojej fabryce produkujesz dwa rodzaje kolorowego papieru: jeden czerwony, a drugi niebieski.
Każdy czerwony papier ma napisany na sobie ciąg $S$: składa się on z $|S|$ jednostkowych kwadratów w rzędzie, a $S_i$ jest napisane na $i$-tym kwadracie od lewej.
Każdy niebieski papier ma napisany na sobie ciąg $T$: składa się on z $|T|$ jednostkowych kwadratów w rzędzie, a $T_i$ jest napisane na $i$-tym kwadracie od lewej.
Planujesz stworzyć nowy rodzaj papieru, zwany papierem dwukolorowym, z papieru czerwonego i niebieskiego. W tym celu utniesz kawałek czerwonego papieru, pozostawiając ciągły fragment o dodatniej długości całkowitej, a następnie zrobisz to samo z kawałkiem niebieskiego papieru. Potem skleisz koniec czerwonego kawałka z początkiem niebieskiego kawałka.
Na przykład, załóżmy, że $S$ to abcde, a $T$ to fghij. Możesz stworzyć papier dwukolorowy z napisem bcdfg lub abcij. Nie możesz jednak stworzyć papieru dwukolorowego z napisem acdghij lub fghij. (Tutaj podkreślony ciąg oznacza czerwony kawałek, a reszta oznacza niebieski kawałek.) Dwa kawałki papieru dwukolorowego uważa się za takie same, jeśli mają na sobie ten sam czerwony ciąg i ten sam niebieski ciąg.
Spośród wszystkich różnych kawałków papieru dwukolorowego, które można wykonać, chcesz poznać ten, który ma leksykograficznie $K$-ty najmniejszy napis. Zauważ, że mogą istnieć papiery z takimi samymi napisami, ale o różnych długościach czerwonego papieru: w takim przypadku możesz je uporządkować dowolnie.
Wejście
Pierwsza linia zawiera ciąg $S$. Druga linia zawiera ciąg $T$. Trzecia linia zawiera liczbę całkowitą $K$.
- $1 \le |S| \le 75\,000$
- $1 \le |T| \le 75\,000$
- $S$ oraz $T$ składają się z małych liter alfabetu angielskiego
- $1 \le K \le 8 \cdot 10^{18}$
Wyjście
Jeśli całkowita liczba możliwych papierów dwukolorowych jest ściśle mniejsza niż $K$, wypisz $-1$. W przeciwnym razie wypisz leksykograficznie $K$-ty najmniejszy ciąg spośród wszystkich możliwych do wykonania papierów dwukolorowych.
Przykład
Wejście 1
tww wtw 21
Wyjście 1
wwtw