Дилатация – один из простейших методов морфологической обработки изображений. Его основное назначение – расширять объекты изображения путем применения некоторого ядра.
Пусть у нас есть некоторое исходное изображение $$$A$$$ состоящее только из черных (объекты) и белых (фон) точек. Если для дилатации (dilation) используется ядро размером $$$3 \times 3$$$, то в целевом изображении $$$B$$$ точка $$$B_{i, j}$$$ будет черной, если она была черной на исходном изображении ($$$A_{i, j}$$$ – черная) или черной была хотя бы одна из соседних точек (некоторых соседей может не быть): $$$A_{i - 1, j - 1}$$$, $$$A_{i - 1, j}$$$, $$$A_{i - 1, j + 1}$$$, $$$A_{i, j - 1}$$$, $$$A_{i, j + 1}$$$, $$$A_{i + 1, j - 1}$$$, $$$A_{i + 1, j}$$$ или $$$A_{i + 1, j + 1}$$$.
Допустим, что у Вас имеется обработанное изображение $$$B$$$, сможете ли Вы восстановить исходное? Напишите программу, которая по изображению $$$B$$$ построит то, из которого $$$B$$$ получилось после дилатации с использованием ядра размером $$$3 \times 3$$$, если это возможно.
Первая строка содержит числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 100$$$) – количество строк и столбцов в изображении соответственно.
Далее следуют $$$n$$$ строк, каждая из которых содержит $$$m$$$ символов. Каждый символ описывает точку изображения. Белая точка обозначается точкой «.», а черная - символом решетки «#». Гарантируется, что других символов в строках нет.
Первая строка должна содержать слово «Possible», если подобрать исходное изображение возможно, или «Impossible» – если нельзя.
Если было выведено слово «Possible», то далее следует $$$n$$$ строк, каждая из которых содержит $$$m$$$ символов – предположительное исходное изображение, закодированное так же, как и входное.
Если существует несколько решений, выведите любое из них.
5 5......###..###..###......
Possible ..... ..... ..#.. ..... .....
3 3....#....
Impossible
