8. Malé preusporiadanie

Spartakus sa smutne pozerá na svoju armádu zdecimovanú poslednou bitkou. Vojaci stoja vo štvorcovej formácii – falange. Na mnohých miestach, kde by mal stáť vojak, je však iba prázdny priestor pripomínajúci hrdinského bojovníka padnuvšieho v boji.

S deravými šíkmi sa však bojovať nedá. Vojakov preto treba preusporiadať do kompaktnejšieho útvaru. Spartakus nemá čas každému vojakovi osobitne určovať nové miesto vo formácii. Preto sa rozhodol iba vymeniť niektoré stĺpce falangy. Jeho cieľom je, aby v žiadnom rade formácie neboli diery – teda aby všetci vojaci v danom rade stáli tesne pri sebe (a mohli zo svojich štítov vytvoriť stenu). Ale dá sa to vôbec?

Úloha

Formáciu vojakov si môžeme predstaviť ako štvorec rozdelený na \(n \times n\) políčok. Každé políčko je buď prázdne, alebo na ňom stojí vojak. Vašou úlohou bude preusporiadať stĺpce tohto štvorca tak, aby v každom riadku platilo, že všetci vojaci stojaci v tomto riadku tvoria jeden súvislý úsek (alebo nula súvislých úsekov, ak v danom riadku žiadni vojaci nie sú). Ak nie je možné formáciu preusporiadať takýmto spôsobom, podajte o tom správu.

Formát vstupu

Prvý riadok vstupu obsahuje jedno celé číslo \(n\) (\(1 \leq n \leq 500\)) – rozmer formácie. Nasleduje \(n\) riadkov po \(n\) znakov popisujúcich formáciu. Políčka s vojakmi sú značené znakom "*", prázdne políčka sú značené znakom ".". Znaky v týchto riadkoch nie sú oddelené medzerami.

Formát výstupu

V prípade, že stĺpce formácie sa dajú preusporiadať tak, aby v žiadnom riadku neboli diery, vypíšte na prvý riadok výstupu slovo "ANO" (bez úvodzoviek). Následne vypíšte \(n\) riadkov po \(n\) znakov – popis formácie po preusporiadaní, v rovnakom formáte, ako na vstupe. Ak existuje viacero riešení, vypíšte ľubovoľné z nich.

Ak sa stĺpce formácie nedajú preusporiadať vhodným spôsobom, vypíšte iba jeden riadok obsahujúci slovo "NIE".

Príklady

Input:

6
*...*.
**.**.
......
.*..*.
...*..
.**..*

Output:

ANO
.**...
****..
......
..**..
*.....
...***

Stĺpec, ktorý bol pôvodne prvý, sme presunuli na druhé miesto, druhý stĺpec na štvrté, tretí na piate, štvrtý na prvé, piaty na tretie a šiesty sme nechali na mieste.

Input:

3
**.
*.*
.**

Output:

NIE