CF1227E.Arson In Berland Forest

The Berland Forest can be represented as an infinite cell plane. Every cell contains a tree. That is, contained before the recent events.

A destructive fire raged through the Forest, and several trees were damaged by it. Precisely speaking, you have a $n \times m$ rectangle map which represents the damaged part of the Forest. The damaged trees were marked as "X" while the remaining ones were marked as ".". You are sure that all burnt trees are shown on the map. All the trees outside the map are undamaged.

The firemen quickly extinguished the fire, and now they are investigating the cause of it. The main version is that there was an arson: at some moment of time (let's consider it as $0$) some trees were set on fire. At the beginning of minute $0$, only the trees that were set on fire initially were burning. At the end of each minute, the fire spread from every burning tree to each of $8$ neighboring trees. At the beginning of minute $T$, the fire was extinguished.

The firemen want to find the arsonists as quickly as possible. The problem is, they know neither the value of $T$ (how long the fire has been raging) nor the coordinates of the trees that were initially set on fire. They want you to find the maximum value of $T$ (to know how far could the arsonists escape) and a possible set of trees that could be initially set on fire.

Note that you'd like to maximize value $T$ but the set of trees can be arbitrary.

伯兰德森林可以表示为一个无限的方格平面，每个方格中都生长着一棵树——至少在最近的事件发生之前是这样。

一场具有破坏性的火灾席卷了整片森林，其中若干棵树因此受损。更准确地说，你拥有一张 $n \times m$ 的矩形地图，它表示森林中受损的部分。受损的树被标记为 “X”，而未受损的树则被标记为 “.”。你确信地图上已完整标出了所有被烧毁的树；地图之外的所有树均未受损。

消防员迅速扑灭了大火，现在正着手调查起火原因。目前最主要的假设是有人纵火：在某一时刻（我们将其记为 $0$），某些树被人为点燃。在第 $0$ 分钟初，仅有最初被点燃的那些树处于燃烧状态；而在每一分钟结束时，火焰会从每一棵正在燃烧的树蔓延至其周围全部 $8$ 个相邻方格（即包括对角线方向）中的树；至第 $T$ 分钟初，大火被完全扑灭。

消防员希望尽快抓获纵火者。问题在于，他们既不知道 $T$ 的具体取值（即火灾持续了多长时间），也不知道最初被点燃的树的位置坐标。他们请你找出最大的可能的 $T$ 值（以估算纵火者可能逃逸的距离），并给出一组可能的、最初被点燃的树的位置。

注意：你的目标是使 $T$ 尽可能大，但所给出的初始着火点集合可以是任意的。

The first line contains two integer $n$ and $m$ ($1 \le n, m \le 10^6$, $1 \le n \cdot m \le 10^6$) — the sizes of the map.

Next $n$ lines contain the map. The $i$-th line corresponds to the $i$-th row of the map and contains $m$-character string. The $j$-th character of the $i$-th string is "X" if the corresponding tree is burnt and "." otherwise.

It's guaranteed that the map contains at least one "X".

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 10^6$，且 $1 \le n \cdot m \le 10^6$）—— 表示地图的尺寸。

接下来的 $n$ 行描述该地图。其中第 $i$ 行对应地图的第 $i$ 行，包含一个长度为 $m$ 的字符串。该字符串中第 $j$ 个字符为 "X" 表示对应位置的树已被烧毁，为 "." 则表示未被烧毁。

保证地图中至少包含一个字符 "X"。

In the first line print the single integer $T$ — the maximum time the Forest was on fire. In the next $n$ lines print the certificate: the map ($n \times m$ rectangle) where the trees that were set on fire are marked as "X" and all other trees are marked as ".".

第一行输出一个整数 $T$ —— 森林着火的最长时间。
接下来的 $n$ 行输出验证方案：一张 $n \times m$ 的矩形地图，其中被点燃的树标记为 "X"，其余树标记为 "."。