Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Adamovi na [email protected]
V múzeu praskov dostali novú zbierku obrazov. Podľa popisu zásielky majú obsahovať mozaiky rôznych veľkostí a tvarov. Kurátor múzea a jeho tím však potrebujú rýchlo zistiť ktoré časti plátna zapĺňajú takéto mozaiky, aby ich mohli vystaviť. Výstavu potrebujú otvoriť o jeden ďeň a nemajú dostatok času na manuálnu kontrolu, preto o pomoc požiadali vás. Keďže stroj na rezanie plátna potrebuje špeciálne značenie, je nutné každú mozaiku orámovať.
Vašou úlohou je napísať program, ktorý na vstupe dostane obraz veľkosti $r \times s$ znakov. Každý obraz pozostáva zo znakov anglickej abecedy a bodiek (.). Bodka znamená, že na danom mieste sa nenachádza časť mozaiky. V obraze je potrebné mozaiku nájsť a čo najtesnejšie ju orámovať obdĺžnikom tvoreným zo znakov mriežky (#). Mozaika nemusí byť súvislá, môže obsahovať “diery”, vždy však stačí použiť iba jeden rám.
Na prvom riadku sa nachádzajú dve čísla $r$ a $s$ (platí $1 \leq r, s \leq 800$), výška a šírka obrazu. Na nasledujúcich $r$ riadkoch sa nachádza reťazec dĺžky $s$ pozostávajúci zo znakov anglickej abecedy a bodiek (.). Môžete počítať s tým, že obraz nie je prázdny, teda obsahuje aspoň jeden znak odlišný od bodky.
V prípade, že mozaiku ide zarámovať, vypíšte obraz zo vstupu obsahujúci orámovanie zložené zo znakov # ($r$ riadkov po $s$ znakoch). Ak by rám presahoval rozmery obrazu, vypíšte na jediný riadok výstupu Neda sa.
4 4
....
.xy.
.zq.
....
####
#xy#
#zq#
####
4 4
....
..a.
..a.
.b..
Neda sa
(Mozaiku nejde orámovať, pretože jeden z jej znakov (b) sa dotýka steny obrazu. Rám by tak presahoval obraz.)
7 6
......
......
..aa..
......
..bb..
......
......
......
.####.
.#aa#.
.#..#.
.#bb#.
.####.
......
18 30
..............................
..............................
...........qqj................
...........qqq................
........j..kqqk.j--...jpkqp...
........qqkkq-qkqq-p-kkqkp....
..kqkk---qqkk--k-kk-p-kp......
...j-qqkkkk---ppp-p-kkjjjj....
......-qqk------------kqqkp...
....kqqqqq---prask--kk-pj.....
.......pqk----------kp........
......kqkkqqqppkk-pp-k-.......
....jqqqk-jpqpkkp-k-ppkkj.....
...jqk-j...pqkk....pkk--kp....
...........pqkj......j-kkq-...
............pj..........j-k-..
..............................
..............................
..............................
.############################.
.#.........qqj..............#.
.#.........qqq..............#.
.#......j..kqqk.j--...jpkqp.#.
.#......qqkkq-qkqq-p-kkqkp..#.
.#kqkk---qqkk--k-kk-p-kp....#.
.#.j-qqkkkk---ppp-p-kkjjjj..#.
.#....-qqk------------kqqkp.#.
.#..kqqqqq---prask--kk-pj...#.
.#.....pqk----------kp......#.
.#....kqkkqqqppkk-pp-k-.....#.
.#..jqqqk-jpqpkkp-k-ppkkj...#.
.#.jqk-j...pqkk....pkk--kp..#.
.#.........pqkj......j-kkq-.#.
.#..........pj..........j-k-#.
.############################.
..............................