#B1347. 图像扩散还原

图像扩散还原

【题目描述】

给定一个只包含 # 与 . 的目标图像。

一次图像处理会把原图中每个 # 格子周围九宫格内的格子都变成 #。

请判断是否存在某个原图经过一次处理后得到目标图像;若存在,输出任意一个原图。


【输入描述】

第一行输入两个整数 H,WH,W。

接下来 HH 行输入目标图像。

保证:

  • 1≤H,W≤1001\le H,W\le 100;
  • 图像只包含 # 与 .。

【输出描述】

若不存在,输出 impossible。

若存在,第一行输出 possible,接下来输出一个可行原图。


【样例 1】

【样例 1 输入】

4 4
##..
##..
..##
..##

【样例 1 输出】

possible
#...
....
....
...#

【样例 2】

【样例 2 输入】

4 4
###.
##.#
..##
..##

【样例 2 输出】

impossible