La distancia de edición de dos cadenas ~S~ y ~T~ es el número mínimo de operaciones de edición que se deben realizar para transformar ~S~ en ~T~. Las operaciones de edición válidas son:

• Inserte un solo carácter en cualquier posición.

• Modifica un carácter existente.

• Elimina un carácter existente.

Por ejemplo, la distancia de edición de "pantera" y "aorta" es 5, porque la siguiente cadena de ediciones es válida (y no hay una cadena más corta): pantera -> antera -> aotera -> aoera -> aora -> aorta. En este problema, dado un valor ~K~ y una palabra ~S~, necesitamos construir una palabra ~T~ tal que la distancia de edición de ~S~ y ~T~ sea como mucho ~K~. Hay, por supuesto, varias posibilidades para eso, por lo que le pediremos que elija la palabra ~T~ que viene primero alfabéticamente. Una palabra viene siempre alfabéticamente después de cualquier prefijo apropiado. Entre dos palabras que no son prefijos el uno del otro, la que viene primero alfabéticamente es la que tiene, en la primera posición en la que se diferencian de izquierda a derecha, una letra más cercana al principio del alfabeto. Observe que la palabra vacía (que tiene cero caracteres) es una palabra válida y está alfabéticamente antes de cualquier otra palabra.

Entrada

La entrada contiene varios casos de prueba. Cada caso de prueba se describe en una sola línea que contiene un entero ~K~ ~(0 \leq K \leq 1000)~ y una palabra no vacía ~S~ de un máximo de ~2000~ letras minúsculas, separadas por un solo espacio. La última línea de la entrada contiene el número ~-1~ y un asterisco separados por un solo espacio y no debe ser procesado como un caso de prueba.

Salida

Para cada caso de prueba, genere una sola línea con una palabra ~T~ de letras minúsculas, de modo que la distancia de edición de ~S~ y ~T~ sea como mucho ~K~. Si hay varias palabras en esa situación, emita la que viene primero alfabéticamente.

Ejemplo de Entrada

4 abcadef
1000 zero
0 zero
-1 *

Ejemplo de Salida

aaaaaadef

zero