Alice har klatret på karrierestigen i mange år og har endelig nådd helt til topps. Hun har nettopp blitt administrerende direktør (CEO) i et stort børsnotert selskap. Den forrige direktøren fikk sparken på grunn av dårlige økonomiske resultater, men Alice vet svært godt hvordan man øker fortjenesten. Det er på tide å velge et nytt firmanavn!
Investorer elsker enhver omtale av kunstig intelligens, spesielt i firmanavnet. Grunnverdien til selskapet er lik lengden på navnet, og hver forekomst av delstrengen «AI» multipliserer selskapets verdi med 5. For eksempel har navnet «AAICPCAIIA» lengde 10 og to (understrekede) forekomster av «AI»:
- $\operatorname{value}(\texttt{AAICPCAIIA}) = 10 \cdot 5 \cdot 5 = 250$
Flere eksempler:
- $\operatorname{value}(\texttt{AXI}) = 3$ (null forekomster av «
AI») - $\operatorname{value}(\texttt{AIAIAIAI}) = 8 \cdot 5 \cdot 5 \cdot 5 \cdot 5 = 5000$ (fire forekomster av «
AI») - $\operatorname{value}(\texttt{AIMPPZ}) = 6 \cdot 5 = 30$ (én forekomst av «
AI»)
Kontrakten til Alice garanterer henne en eksepsjonelt raus bonus dersom selskapets verdi er nøyaktig $n$. Hun ønsker også at navnet skal være så kort som mulig.
Alice er allerede opptatt med sin neste oppgave – å designe den oppfriskede logoen. Kan du foreslå et nytt firmanavn i mellomtiden? Finn det kortest mulige ordet med verdi $n$, bestående av store engelske bokstaver A-Z.
Inndata
Den eneste linjen inneholder et heltall $n$ ($1 \le n \le 100\,000$) – den ønskede selskapsverdien.
Utdata
Skriv ut et ord bestående av bokstavene A-Z – et navn med verdi $n$ og minst mulig lengde. Hvis det finnes mange løsninger, kan du skrive ut hvilken som helst av dem.
Eksempler
Inndata 1
30
Utdata 1
AIMPPZ
Inndata 2
250
Utdata 2
AAICPCAIIA
Merk
I den første testen ser vi etter det kortest mulige navnet med verdi 30. Optimale ord har lengde 6 og én forekomst av «AI», for eksempel «AIMPPZ», «HUAWAI», «BRAINS» og «AAAIII». Ingen kortere ord har verdi 30.
I den andre testen kan verdien 250 ikke oppnås med et navn som er kortere enn 10 tegn.