Con el fin de proteger información se utilizan diferentes técnicas de cifrado cuyo propósito es ocultar la información real sin alterar su estructura. El cifrado utiliza claves que pueden ser iguales, esto quiere decir que con la clave que se cifra se descifra, o diferentes con la que se cifra no se descifra, o híbrida.

Se va a cifrar una conjunto de n nombres de estudiantes utilizando la clave c donde (0 ≤ c ≤ 3) y reemplazado cada carácter por el código ASCII en Hexadecimal respectivo en bloques de 2 números, más la clave. Adicionalmente el nombre se guarda en la posición en orden alfabético de un vector.

Input

La entrada consistirá en un número que corresponde a la clave, (Entre 0 y 3. Se debe validar), y una serie de líneas, cada línea tiene un nombre. La entrada terminará cuando la línea tenga un *.

Output

Output description...

Example

Input:
2
Juan
JUAN1
Lazaro?
Pedrito
*

Output:
4C776370
4C57435033
4E637C63747141
526766746B7671