Restoring a Picture

There is an N by M picture. Each cell is either white or black. White cells are written as ., and black cells are written as #.

Two black cells are directly connected if they share a side. Two black cells A and B are indirectly connected if there is a path of black cells A = P1, P2, ..., Pk = B such that every consecutive pair Pi and Pi+1 is directly connected.

A black group is a set of black cells connected directly or indirectly. Different groups must not be connected to each other.

Every black group in the original picture satisfies this property: for any two black cells in the same group, there is a path using only black cells of that group whose length is equal to the Manhattan distance between the two cells.

For two cells A(Xa, Ya) and B(Xb, Yb), their Manhattan distance is |Xa - Xb| + |Ya - Yb|.

During transmission, some black cells changed to white. No white cell changed to black.

Change some white cells in the received picture back to black so that the resulting picture satisfies the original property. Output the picture with the minimum possible number of changed cells.

The first line contains the height N and width M of the picture.

The next N lines contain the received picture. Each line is a string of length M consisting only of . and #.

1 <= N, M <= 50

Output the restored picture using N lines, starting from the first row.

The restored picture with the minimum number of changes is unique.