5. Koho ešte nepoznám?

Prvácky týždeň na Matfyze je v plnom prúde. Budúci študenti (medzi ktorými je mimochodom aj Duško) si užili mnoho prednášok, spoznávacích hier a iných blbostí, ktoré Dušan už dávno poznal (veď Matfyz je už dávno jeho druhým domovom a do T2 už chodí aj spávať). Takto znudený sa teda rozhodol, že na budúcich študenton FIIT-ky nastraží habaďúru. Počas spoločnej zoznamovačky sa nenápadne vytratil a začal snovať plán, ako uväzniť FIITákov na Matfyze. A čo je ešte lepšie, o chvíľu bude obed a ak cesty zatarasí dostatočne dobre, tak FIITáci nestihnú prísť do Eat&Meetu ¹ načas. Treba si len dať pozor na to, aby nevymkol aj nejakého zo svojich kamarátov.

Úloha

Pôdorys Matfyzu si vieme predstaviť ako štvorčekovú mriežku s \(n\) riadkami a \(m\) stĺpcami. Každé políčko môže byť zablokované #, prázdne . alebo na ňom môže stáť človek ( F ak to je FIITák alebo M ak je Matfyzák). V pravom dolnom rohu mapky sa nachádza východ, cez ktorý sa dá dostať do Eat&Meetu. Dušan chce na FIITákov nastražiť nasledovnú habaďúru. Zablokuje nejaké prázdne políčka Matfyzu tak, aby sa žiaden FIITák nevedel dostať von z Matfyzu, ale každý Matfyzák sa z neho vedel dostať. Každý človek vie chodiť len po hranou susediacich políčkach. Pomôžte Dušanovi zistiť, ktoré políčka má zablokovať alebo povedzte, že sa to proste nedá.

Formát vstupu

V prvom riadku vstupu sú čísla \(n\) a \(m\) (\(1 \leq n, m \leq 600\)) udávajúce rozmery Matfyzu. Nasleduje \(n\) riadkov a na každom z nich \(m\) znakov ., #, M alebo F popisujúce aktuálny stav Matfyzu a rozmiestnenie ľudí. Je garantované, že pravé dolné políčko (teda východ) je vždy prázdne.

V jednotlivých sadách platia nasledujúce obmedzenia:

Formát výstupu

Vypíšte Plan uspesny, ak sa dajú zablokovať niektoré políčka tak, aby sa všetci Matfyzáci vedeli dostať z Matfyzu von a všetci FIITáci nie. Potom vypíšte \(n\) riadkov a na každom z nich \(m\) znakov reprezentujúcich to, ako môže vyzerať Matfyz po pridaní prekážok, aby Dušanova habaďúra vyšla. Ak existuje viac možností, vypíšte ľubovoľnú z nich. Ak sa to nedá, vypíšte len na jeden riadok Neda sa.

Nezabudnite posledný riadok ukončiť znakom konca riadku.

Príklady

Input:

3 3
M..
..F
M..

Output:

Neda sa

Jediný spôsob, ako zabrániť FIITákovi sa dostať z univerzity von je, ak zablokujeme východ. Potom sa ale z univerzity nebudú vedieť dostať ostatní Matfyzáci.

Input:

5 5
...F.
F....
..###
##M..
M....

Output:

Plan uspesny
...F.
F....
..###
##M..
M....

Netreba pridávať žiadne prekážky, žiaden FIITák sa nedokáže dostať z univerzity.

Input:

2 5
F.MMM
.F.M.

Output:

Plan uspesny
F#MMM
.F#M.