Wieże [B]

Limit pamięci: 32 MB

Po długich staraniach Bajtek zdołał rozmieścić wież na szachownicy rozmiaru , tak że żadne dwie wieże nie szachują się. Dla przypomnienia: wieża szachuje wszystkie pola szachownicy znajdujące się w tym samym wierszu lub w tej samej kolumnie co ona¹.

Niestety, chłopiec przypadkowo potrącił szachownicę, przez co niektóre z wież poprzewracały się i spadły. Czy pomógłbyś mu ustawić te wieże z powrotem? Bajtek prosi, żeby nie ruszać wież, które wciąż stoją na szachownicy.

Wejście

W pierwszy wierszu standardowego wejścia znajduje się jedna liczba całkowita (), oznaczająca rozmiar szachownicy. Dalej następuje opis ustawienia wież na szachownicy: kolejne wierszy zawiera po znaków każdy. Znak `.' oznacza puste pole, a litera `W' reprezentuje pole zajmowane przez wieżę.

Możesz założyć, że na szachownicy stoi wież, przy czym , oraz że żadna para stojących wież nie szachuje się.

Wyjście

Twój program powinien wypisać na standardowe wyjście reprezentację odpowiednio zapełnionej szachownicy w postaci wierszy zawierających po znaków `.' lub `W' każdy. Na planszy powinno występować dokładnie znaków `W' reprezentujących wieże, przy czym wież powinno stać dokładnie na takich samych pozycjach jak na wejściu. Żadne dwie wieże nie mogą się szachować. Jeśli istnieje więcej niż jeden sposób dostawienia wież, Twój program może wypisać dowolny z nich.

Przykład

Dla danych wejściowych:

8
........
.....W..
..W.....
.......W
W.......
........
.W......
........

poprawną odpowiedzią jest:

...W....
.....W..
..W.....
.......W
W.......
....W...
.W......
......W.

¹ Patrz także http://pl.wikipedia.org/wiki/Wieża_(szachy).

Autor zadania: Jakub Radoszewski.