4. Dezinfekcia

Krajské Mesto Pravičiarov (KMP) čelí architektonickej výzve. Z dlhodobých pozorovaní obyvatelia zistili, že počas roka sa vyskytujú, čím ďalej, tým výraznejšie extrémy, čo sa týka množstva pitnej vody v ich oblasti. Niekedy majú pitnej vody veeeľmi veľa a inokedy veeeľmi málo. Preto prišli s nápadom, že potrebujú zväčšiť mestskú nádrž na vodu, aby počas priaznivejšieho obdobia dokázali uskladniť prebytočnú vodu na horšie časy.

Nádrž sa nachádza v podzemí mesta tvoreného skalami¹. Ich podzemie je tiež zaujímavé tým, že skaly je možné odstraňovať (pri pohľade z hora) iba po štvorcových kusoch s rozmermi \(1m \cdot 1m\). Nádrž je tvorená iba súvislým voľným priestorom medzi skalami. Skaly sú vodotesné a teda cez ne nepresakuje voda.

Jeden by si povedal, že tu o nič nejde. Stačí bezhlavo vykopať väčšiu dieru. No ako to už v takýchto KSP úlohách býva, je tu háčik - v podzemí sa nachádzajú aj viaceré menšie nádrže na dezinfekciu, ktoré boli vytvorené iba nedávno. Problém je teda v tom, že obyvatelia neobľubujú konzumáciu dezinfekčných prostriedkov. Preto je pri plánovaní rozšírenia nádrže potrebné dbať na to, aby sa dezinfkecia nezmiešala s pitnou vodou.

Analytici z KMP zistili, že je potrebné, aby bola plocha nádrže zväčšená aspoň na \(s\) metrov štvorcovích. V úlohe projektovania nových stavebných úprav si však až tak neveria. Preto ste tu vy. Pomôžte obyvateľom KMP vyriešiť tento problém!

Úloha

Poznáme pôdorys podzemia - 2D štvorčeková mriežka, kde jeden štvorček má rozmery \(1m \cdot 1m\). Odstráňte z neho najmenší možný počet skál tak, aby vo výslednom pôdoryse zaberala nádrž na pitnú vodu aspoň \(s\) metrov štvorcovích a aby sa do nej nevylial obsah niektorej nádrže na dezinfekciu.

Každá nádrž na dezinfekciu je reprezentovaná znakom D a má rozmery presne \(1m \cdot 1m\), čiže okolo každého znaku D sa na každom z existujúcich štyroch susedných políčok nachádza skala (#).

Nádrž na pitnú vodu je tvorená políčakmi označenými znakom .. Všetky políčka nádrže na vodu tvoria práve jednu súvislú nádrž. Inými slovami, z každého políčka nádrže na pitnú vodu je možné sa dostať na každé políčko nádrže na pitnú vodu prechodom iba cez políčka nádrže na pitnú vodu.

Výsledná nádrž musí byť takisto súvislá. Obyvatelia nebudú spokojní s riešením, ktoré zapríčiní existenciu viac ako jednej nádrže na pitnú vodu v podzemí ich KMP.

Vypíšte mapu podzemia, ktoré spĺňa zadané požiadavky!

Formát vstupu

Na prvom riadku vstupu sa nachádzajú 3 čísla. Rozmery mapy podzemia - počet riadkov \(m\) a počet stĺpcov \(n\) - a požadovaná plocha nádrže \(s\). Platí, že \(1 \leq m, n \leq 1\,000\) a \(1 \leq s \leq m \cdot n\). Nasleduje \(m\) riadkov po \(n\) znakov reprezentujúcich mapu. Môžu sa tu vyskytovať iba znaky . (nádrž na pitnú vodu), # (skala) a D (dezinfekcia).

Formát výstupu

Na výstup vypíšte mapu, ktorá vznikla splnením úlohy! Vypíšte ju v rovnakom formáte, v akom bola na vstupe - \(m\) riadkov po \(n\) znakov!

Pre jeden vstup môže existovať viacero správnych riešení. V takom prípade vypíšte ľubovoľné z nich!

Môžete počítať s tým, že pre každý testovací vstup existuje riešenie.

Príklady

Input:

6 6 10
###.##
#D#..#
###..#
##..##
##.###
######

Output:

##..##
#D#..#
##...#
##..##
##.###
######

Jedným riešením je odstránenie skál v rohoch okolo D. (Ak sa skaly dotýkajú hranami, spojenie je stále vodotesné a obyvatelia nebudú otrávení.)

Input:

6 6 20
###.##
#D#..#
###..#
##..##
##.#D#
######

Output:

##....
#D#...
.#....
....#.
...#D#
######