Berland 森林可以表示为无限的单元平面。每个细胞都包含一棵树。也就是说,包含在最近发生的事件之前。
一场毁灭性的大火席卷了森林,数棵树被烧毁。准确地说,您有一个 $$$n \times m$$$ 矩形地图,它代表森林的受损部分。受损树木标记为“X”,其余树木标记为“.”。您确定所有被烧毁的树木都显示在地图上。地图外的所有树木均未受损。
消防人员迅速将火扑灭,目前正在调查起火原因。主要版本是发生了纵火事件:在某个时刻(让我们将其视为$$$0$$$)一些树木被点燃。在分钟$$$0$$$开始时,只有最初着火的树木正在燃烧。每分钟结束时,火势都会从每棵燃烧的树蔓延到每棵相邻的 $$$8$$$ 树。 $$$T$$$分钟开始时,火被扑灭。
消防员希望尽快找到纵火犯。问题是,他们既不知道 $$$T$$$ 的值(大火燃烧了多长时间),也不知道最初着火的树木的坐标。他们希望你找到 $$$T$$$ 的最大值(以了解纵火犯能逃多远)以及一组可能最初被点燃的树木。
请注意,您希望最大化价值$$$T$$$,但树的集合可以是任意的。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 10^6$$$, $$$1 \le n \cdot m \le 10^6$$$) — 地图的大小。
接下来的 $$$n$$$ 行包含地图。第 $$$i$$$ 行对应于地图的第 $$$i$$$ 行,并包含 $$$m$$$ 字符串。如果相应的树被烧毁,则第 $$$i$$$ 字符串的第 $$$j$$$ 个字符为“X”,而“.”。否则。
保证地图至少包含一个“X”。
输出
在第一行中打印单个整数 $$$T$$$ — 森林着火的最长时间。在接下来的 $$$n$$$ 行中打印证书:地图($$$n \times m$$$ 矩形),其中被点燃的树木被标记为“X”,所有其他树木被标记为“.”。
示例
输入 #1
3 6 XXXXXX XXXXXX XXXXXX
输出 #1
1 ...... .X.XX. ......
输入 #2
10 10 .XXXXXX... .XXXXXX... .XXXXXX... .XXXXXX... .XXXXXXXX. ...XXXXXX. ...XXXXXX. ...XXXXXX. ...XXXXXX. ..........
输出 #2
2 .......... .......... ...XX..... .......... .......... .......... .....XX... .......... .......... ..........
输入 #3
4 5 X.... ..XXX ..XXX ..XXX
输出 #3
0 X.... ..XXX ..XXX ..XXX