2. Rámovanie

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ť.

Úloha

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.

Formát vstupu

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.

Formát výstupu

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.

Príklad

Input:

4 4
....
.xy.
.zq.
....

Output:

####
#xy#
#zq#
####

Input:

4 4
....
..a.
..a.
.b..

Output:

Neda sa

(Mozaiku nejde orámovať, pretože jeden z jej znakov (b) sa dotýka steny obrazu. Rám by tak presahoval obraz.)

Input:

7 6
......
......
..aa..
......
..bb..
......
......

Output:

......
.####.
.#aa#.
.#..#.
.#bb#.
.####.
......

Input:

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-..
..............................
..............................

Output:

..............................
.############################.
.#.........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-#.
.############################.
..............................