Webový portál

Na webový portál sa registrujú noví užívatelia. Ak už je ich želané meno, napríklad roderick, obsadené, portál im láskyplne ponúkne číslovanú náhradu, napríklad roderick47. (Podobnosť príbehu s našim univerzitným loginom je čisto náhodná :) ) V tejto úlohe budete implementovať túto funkcionalitu, pričom budeme predpokladať nasledovné skutočnosti:

1. Každé želané meno je buď tvorené len malými písmenami (anglickej abecedy), alebo najskôr malými písmenami (tvoriacimi tzv. základné meno) a potom kladným celým číslom (tvoriacim tzv. sufix).
2. Ak je želané meno k dispozícii, užívateľ ho dostane.
3. Ak nie, ponúkneme mu najlepšiu možnosť, ktorú ešte máme k dispozícii, v poradí: najskôr samotné základné meno a následne základné meno s číselnými sufixami 1, 2, 3, atď.
4. Užívateľ vždy ponúknuté meno akceptuje.

Odporúčanie: Už by ste mali poznať niektoré vhodné dátové štruktúry. Použitie vhodnej dátovej štruktúry vám vie výrazne uľahčiť život. Ak na veľkých vstupoch prekračujete časový limit, niečo robíte principiálne zle. A dotyčné „niečoˇ, ktoré robíte zle, je skoro určite hľadanie mena, ktoré užívateľovi ponúknuť

Vstup

Vstup obsahuje niekoľko riadkov (aspoň jeden, najviac stotisíc). V každom riadku je jedno želané meno. Dĺžka každého riadku je medzi 1 a 17, vrátane. Každé želané meno má vyššie popísaný tvar a obsahuje aspoň jedno písmeno.

Výstup

Pre každé želané meno vypíšte jeden riadok s menom, ktoré dotyčný užívateľ naozaj dostane

Príklad

jano
baska
jano
jano
michal27
jano4
jano
jano
jano1

jano
baska
jano1
jano2
michal27
jano4
jano3
jano5
jano6

Všimnite si obzvlášť, že predposledný jano dostal meno jano5, keďže jano4 už bolo obsadené skôr.