Garden

There is a rectangular garden in front of Gina's house. The garden can be seen as an n-by-m grid. All cells are identical squares, and two cells are adjacent if they share an edge.

Gina loves cacti and wants to plant as many cacti as possible in the garden. There are constraints on planting cacti.

• The soil in some cells is too wet and is not suitable for cacti. Gina cannot plant cacti in those cells.
• The soil in each cell is not fertile enough to grow two or more cacti, so Gina can plant at most one cactus in a cell.
• At most one cactus can be planted in any pair of adjacent cells. Otherwise, the cacti in those cells may be harmed by their neighbor's thorns.

Write a program that helps Gina compute the maximum number of cacti she can plant and a planting that meets the constraints above.

The first line contains two space-separated integers n and m, meaning the garden is an n-by-m grid. Each of the following n lines contains a string of m characters. These characters are either ‘.’ or ‘*’. The j-th character of the i-th of these lines indicates whether the soil in the cell at row i, column j is suitable for planting a cactus. ‘.’ means it is suitable, and ‘*’ means it is not suitable.

First, output the maximum possible number of cacti on the first line. Then output n lines, each containing a string of m characters. Each character must be one of ‘.’, ‘*’, and ‘C’. The j-th character of the i-th of these lines indicates the status of the cell at row i, column j. A ‘C’ means a cactus should be planted in that cell, and the other cells should be identical to the corresponding positions of the input.

If there is more than one possible planting, any of them will be accepted.

• 1 ≤ nm ≤ 105