선인장

지나의 집 앞에는 직사각형 모양의 정원이 있다. 정원은 n행 m열의 격자로 볼 수 있다. 모든 칸은 같은 크기의 정사각형이며, 두 칸이 변을 공유하면 서로 인접한 것으로 본다.

지나는 선인장을 좋아해서 정원에 선인장을 최대한 많이 심으려고 한다. 하지만 선인장을 심는 데에는 제약이 있다.

• 일부 칸은 흙이 너무 젖어 있어 선인장을 심기에 적합하지 않다. 지나는 그런 칸에는 선인장을 심을 수 없다.
• 각 칸의 흙은 척박해서 선인장 두 그루 이상을 기를 수 없으므로, 한 칸에는 선인장을 최대 한 그루만 심을 수 있다.
• 서로 인접한 두 칸에는 선인장을 최대 한 그루만 심을 수 있다. 그렇지 않으면 이웃한 선인장의 가시에 다칠 수 있기 때문이다.

지나를 도와 주어진 조건을 만족하면서 선인장을 심을 수 있는 최대 개수와, 그 개수만큼 선인장을 심는 방법을 구하는 프로그램을 작성하시오.

첫째 줄에 정원이 n행 m열의 격자임을 나타내는 두 정수 n과 m이 공백으로 구분되어 주어진다. 그다음 n개의 줄에 각각 길이 m인 문자열이 주어진다. 각 문자는 ‘.’ 또는 ‘*’이다. i번째 줄의 j번째 문자는 i행 j열 칸의 흙이 선인장을 심기에 적합한지를 나타낸다. ‘.’은 적합함을, ‘*’은 적합하지 않음을 뜻한다.

첫째 줄에 심을 수 있는 선인장의 최대 개수를 출력한다. 그다음 n개의 줄에 각각 길이 m인 문자열을 출력한다. 각 문자는 ‘.’, ‘*’, ‘C’ 중 하나여야 한다. i번째 줄의 j번째 문자는 i행 j열 칸의 상태를 나타낸다. ‘C’는 그 칸에 선인장을 심어야 함을 뜻하고, 나머지 칸은 입력의 같은 위치에 있던 문자와 같아야 한다.

가능한 심는 방법이 여러 가지라면 그중 아무거나 출력해도 된다.

• 1 ≤ nm ≤ 105