En su fábrica, usted produce dos tipos de papel de color, uno de color rojo y el otro de color azul.
Cada papel de color rojo tiene una cadena $S$ escrita en él: está compuesto por $|S|$ cuadrados unitarios en una fila, y $S_i$ está escrito en el $i$-ésimo cuadrado desde la izquierda.
Cada papel de color azul tiene una cadena $T$ escrita en él: está compuesto por $|T|$ cuadrados unitarios en una fila, y $T_i$ está escrito en el $i$-ésimo cuadrado desde la izquierda.
Usted planea fabricar un nuevo tipo de papel llamado papel de doble color a partir del papel rojo y azul. Para hacerlo, cortará un trozo de papel rojo para dejar una parte continua con una longitud entera positiva, y luego hará lo mismo con un trozo de papel azul. Después de eso, pegará el final del trozo rojo al inicio del trozo azul.
Por ejemplo, suponga que $S$ es abcde y $T$ es fghij. Usted puede hacer un papel de doble color con la cadena bcdfg o abcij escrita en él. Sin embargo, no puede hacer un papel de doble color con la cadena acdghij o fghij escrita en él. (Aquí, la cadena subrayada denota un trozo rojo, y el resto denota un trozo azul). Dos piezas de papel de doble color se consideran iguales si tienen la misma cadena roja y la misma cadena azul escritas en ellas.
Entre todas las diferentes piezas de papel de doble color que se pueden fabricar, usted desea conocer aquella con la $K$-ésima cadena lexicográficamente más pequeña escrita en ella. Tenga en cuenta que puede haber papeles con las mismas cadenas escritas en ellos, pero con diferentes longitudes de papel rojo: en este caso, puede ordenarlos arbitrariamente.
Entrada
La primera línea contiene la cadena $S$. La segunda línea contiene la cadena $T$. La tercera línea contiene el entero $K$.
- $1 \le |S| \le 75\,000$
- $1 \le |T| \le 75\,000$
- $S$ y $T$ consisten en letras minúsculas del alfabeto inglés
- $1 \le K \le 8 \cdot 10^{18}$
Salida
Si el número total de posibles papeles de doble color es estrictamente menor que $K$, imprima $-1$. De lo contrario, imprima la $K$-ésima cadena lexicográficamente más pequeña de todos los posibles papeles de doble color que se pueden fabricar.
Ejemplos
Entrada 1
tww wtw 21
Salida 1
wwtw