Alice ha escalado la escalera corporativa durante muchos años y finalmente ha llegado a lo más alto. Acaba de convertirse en la directora ejecutiva (CEO) de una gran empresa que cotiza en bolsa. El CEO anterior fue despedido debido a los malos resultados financieros, pero Alice sabe perfectamente cómo impulsar las ganancias. ¡Es hora de elegir un nuevo nombre para la empresa!
A los inversores les encanta cualquier mención a la inteligencia artificial, especialmente en el nombre de la empresa. El valor base de la empresa es igual a la longitud de su nombre, y cada aparición de la subcadena "AI" multiplica el valor de la empresa por 5. Por ejemplo, el nombre "AAICPCAIIA" tiene longitud 10 y dos apariciones (subrayadas) de "AI":
- $\operatorname{value}(\texttt{AAICPCAIIA}) = 10 \cdot 5 \cdot 5 = 250$
Más ejemplos:
- $\operatorname{value}(\texttt{AXI}) = 3$ (cero apariciones de "
AI") - $\operatorname{value}(\texttt{AIAIAIAI}) = 8 \cdot 5 \cdot 5 \cdot 5 \cdot 5 = 5000$ (cuatro apariciones de "
AI") - $\operatorname{value}(\texttt{AIMPPZ}) = 6 \cdot 5 = 30$ (una aparición de "
AI")
El contrato de Alice le garantiza una bonificación excepcionalmente generosa si el valor de la empresa es exactamente $n$. También quiere que el nombre sea lo más corto posible.
Alice ya está ocupada con su siguiente tarea: diseñar el logotipo renovado. ¿Puedes proponer un nuevo nombre de empresa mientras tanto? Encuentra la palabra más corta posible con valor $n$, formada por letras inglesas mayúsculas A-Z.
Entrada
La única línea contiene un entero $n$ ($1 \le n \le 100\,000$): el valor deseado de la empresa.
Salida
Imprime una palabra formada por las letras A-Z: un nombre con valor $n$ y la menor longitud posible. Si existen muchas soluciones, imprime cualquiera de ellas.
Ejemplos
Entrada 1
30
Salida 1
AIMPPZ
Entrada 2
250
Salida 2
AAICPCAIIA
Nota
En la primera prueba, buscamos el nombre más corto posible de valor 30. Las palabras óptimas tienen longitud 6 y una aparición de "AI", por ejemplo "AIMPPZ", "HUAWAI", "BRAINS" y "AAAIII". Ninguna palabra más corta tiene valor 30.
En la segunda prueba, no se puede alcanzar el valor 250 con un nombre de menos de 10 caracteres.