Zadanie

Chvíle povianočné

Počet bodov: 20

Vianoce skončili a Julka má teraz dôležitú úlohu: zvešať všetky vianočné ozdoby z vianočného stromčeka. Bohužiaľ, po skúsenostiach z minulých rokov sa bojí, aby sklenené vianočné ozdoby nerozbila. Stávalo sa jej totiž, že ozdoba sa jej šmykla a ako padala, zhodila so sebou aj daľšie ozdoby. Julka chce teda zvešiavať ozdoby tak, že keby jej aj ozdoba z ruky vypadla, nerozbila by žiadne ďalšie ozdoby.

Jej vianočný stromček si môžeme predstaviť ako trojuholník políčok. Na samom vrchu je jedno políčko, pod ním dve, pod ním tri… Na niektorých políčkach môže byť zavesená ozdoba.

Úloha

Zveste všetky ozdoby zo stromčeka tak, aby ste žiadnu nerozbili. Ozdoby padajú priamo dole. Chcete ich zvesiť tak, aby ste nikdy nezvešiavali ozdobu, ktorá má pod sebou inú ozdobu (alebo jej časť). Ozdoby nahraďte malými písmenami anglickej abecedy v poradí, v ktorom ich chcete zvesiť. (Teda a bude prvá zvesená ozdoba, b druhá…) Ozdôb na stromčeku je najviac \(26\).

Vstup a Výstup

Na prvom riadku vstupu dostanete číslo \(n\) - počet riadkov stromčeka. Na nasledujúcich \(n\) riadkoch vstupu je vzhľad vianočného stromčeka. Každý riadok stromčeka sa skladá zo znakov - (reprezentujúci vetvičku) alebo o (reprezentujúci vianočnú guľu). Na \(i\)-tom riadku stromčeka je presne \(i\) znakov.

Na výstup vypíšte ten istý stromček, ale miesto ozdôb vypíšete písmena a - z, ktoré určujú poradie, v ktorom ozdoby zo stromčeka zvešiavate.

Príklad

Input:

4
-
o-
-o-
---o

Output:

-
b-
-a-
---c

Ak by sme najprv zvesili ozdobu b, rozbila by sa nám ozdoba a, preto ozdobu a zvesíme skôr. Ani jedna z ozdôb a a b nerozbije ozdobu c.

Input:

5
-
--
-o-
--oo
---o-

Output:

-
--
-d-
--bc
---a-