Cellular Structure Identification

In a biology class, the teacher introduced the concept of a cell on an N×M grid. The grid contains only the characters '#' and '.'. A cell is made up of a nucleus, cytoplasm, and a cell membrane. The definitions are as follows:

• Nucleus: This is a 4-connected component (neighbors up, down, left, right) of '#' characters. It must be solid, which means that no 4-connected component of '.' is completely enclosed by the nucleus. Here, a 4-connected dot region is said to be completely enclosed if none of its cells touches the grid boundary and for every cell in that dot component every 4-adjacent cell not in the dot region belongs to the nucleus. In mathematical terms, if we denote a dot component by \( D \) and its set of 4‐neighbors (outside \( D \)) by \( N(D) \), then the nucleus is solid if there is no \( D \) such that</p>

  \( \forall d \in D, \; \forall \text{4-neighbor } p \notin D, \; p \in \text{nucleus} \)

• Cell membrane: This is an 8-connected component (neighbors in all 8 directions) of '#' characters that is non‐solid (i.e. it has a hole). The membrane completely encloses a 4-connected region, and within that region there is exactly one nucleus; all other positions in the region are filled with '.'.

Furthermore, every connected component (whether 4-connected or 8-connected) is maximal, meaning it cannot be extended by adding any adjacent '#' (according to the connectivity rules).

Your task is to process the given grid, determine the number of cells present, and then modify the grid such that any '#' that does not belong to any valid cell (i.e. is not part of a nucleus or its corresponding cell membrane) is replaced with '.'.

Input Format: The first line contains two integers N and M. The following N lines each contain a string of M characters, each either '#' or '.'.

Output Format: Output the number of cells detected on the first line. Then output the modified grid, with the same dimensions, where non‐cell '#' characters have been replaced by '.'.

Note: In your solution, you may find it useful to perform flood fills and connected component analyses using 4-connected and 8-connected neighborhood definitions. For a coordinate \((r,c)\), the 4-connected neighbors are \((r-1,c)\), \((r+1,c)\), \((r,c-1)\), and \((r,c+1)\), while the 8-connected neighbors include the four diagonal cells as well.

inputFormat

The first line contains two integers N and M (1 ≤ N, M ≤ 1000), representing the number of rows and columns in the grid. The next N lines each contain a string of M characters, where each character is either '#' or '.'.

outputFormat

On the first line, output an integer representing the number of cells detected. Then output N lines, each containing a string of M characters representing the modified grid, where '#' characters that do not belong to any cell have been replaced with '.'.

sample

3 3
...
.#.
...

0
...
.#.
...