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

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

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 “.”.Examplesinput

3 6 XXXXXX XXXXXX XXXXXX

output

1 ...... .X.XX. ......

input

10 10 .XXXXXX... .XXXXXX... .XXXXXX... .XXXXXX... .XXXXXXXX. ...XXXXXX. ...XXXXXX. ...XXXXXX. ...XXXXXX. ..........

output

2 .......... .......... ...XX..... .......... .......... .......... .....XX... .......... .......... ..........

input

4 5 X.... ..XXX ..XXX ..XXX

output

0 X.... ..XXX ..XXX ..XXX

**Solution:**

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int h, w; cin >> h >> w; vector<string> s(h); for (int i = 0; i < h; i++) { cin >> s[i]; } vector<vector<int>> dist(h, vector<int>(w, -1)); vector<pair<int, int>> qe; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (s[i][j] == '.') { continue; } int border = 0; for (int di = -1; di <= 1; di++) { for (int dj = -1; dj <= 1; dj++) { if (i + di < 0 || j + dj < 0 || i + di >= h || j + dj >= w || s[i + di][j + dj] == '.') { border = 1; break; } } } if (border) { dist[i][j] = 0; qe.emplace_back(i, j); } } } for (int b = 0; b < (int) qe.size(); b++) { int i = qe[b].first; int j = qe[b].second; for (int di = -1; di <= 1; di++) { for (int dj = -1; dj <= 1; dj++) { if (i + di < 0 || j + dj < 0 || i + di >= h || j + dj >= w || s[i + di][j + dj] == '.' || dist[i + di][j + dj] != -1) { continue; } dist[i + di][j + dj] = dist[i][j] + 1; qe.emplace_back(i + di, j + dj); } } } vector<vector<bool>> was(h, vector<bool>(w, false)); vector<tuple<int, int, int>> que; int low = 0, high = (min(h, w) - 1) / 2; while (low < high) { int mid = (low + high + 1) >> 1; que.clear(); for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (dist[i][j] >= mid) { que.emplace_back(i, j, 0); was[i][j] = true; } else { was[i][j] = false; } } } bool fail = false; for (int b = 0; b < (int) que.size(); b++) { int i = get<0>(que[b]); int j = get<1>(que[b]); int d = get<2>(que[b]); if (d == mid) { break; } for (int di = -1; di <= 1; di++) { for (int dj = -1; dj <= 1; dj++) { if (i + di >= 0 && j + dj >= 0 && i + di < h && j + dj < w) { if (s[i + di][j + dj] == '.') { fail = true; break; } if (!was[i + di][j + dj]) { was[i + di][j + dj] = true; que.emplace_back(i + di, j + dj, d + 1); } } else { fail = true; break; } } } if (fail) { break; } } for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (!was[i][j] && s[i][j] == 'X') { fail = true; break; } } if (fail) { break; } } if (fail) { high = mid - 1; } else { low = mid; } } cout << low << '\n'; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (dist[i][j] < low) { s[i][j] = '.'; } } cout << s[i] << '\n'; } return 0; }