안전한 도로망

어떤 도시의 도로망을 하늘에서 내려다보면 $R \times S$ 크기의 단위 정사각형 격자로 보인다. 각 칸은 비어 있거나, 도로 조각 하나가 놓여 있다. 도로 조각은 수직, 대각선, 수평, 교차로 중 하나다. 아래 그림은 그런 도로망 하나를 나타낸다.

격자에는 6가지 문자만 나온다. .(점)은 도로가 지나지 않는 빈 칸이다. -(마이너스)는 수평 도로, /와 \는 대각선 도로, |(파이프)는 수직 도로, +는 교차로다.

자동차가 이웃한 8칸 중 어느 칸에서 가운데 도로 조각으로 들어올 수 있고 또 어느 칸으로 나갈 수 있는지는 아래 표에 나와 있다. *로 표시한 칸은 가운데 도로 조각과 서로 오갈 수 있는 칸이고, #로 표시한 칸은 오갈 수 없는 칸이다.

표를 문자별로 옮기면 이렇다.

• |는 위, 아래 칸과 오갈 수 있다.
• -는 왼쪽, 오른쪽 칸과 오갈 수 있다.
• /는 오른쪽 위, 왼쪽 아래 칸과 오갈 수 있다.
• \는 왼쪽 위, 오른쪽 아래 칸과 오갈 수 있다.
• +는 이웃한 8칸 모두와 오갈 수 있다.

안전한 도로망에는 막다른 길이 없어야 한다. 즉 연결된 이웃 도로 조각이 두 개 미만인 도로 조각이 하나도 없어야 한다. 두 도로 조각이 연결되었다는 말은, 위 표에 따라 첫 번째에서 두 번째로 갈 수 있고 두 번째에서 첫 번째로도 갈 수 있다는 뜻이다. 위 그림의 도로망은 안전하다.

류보가 올해도 말썽을 부렸다. 허가 없이 도로 몇 개를 지어 놓아서, 도로망이 더 이상 안전하지 않을 수도 있다. 도로 조각을 가능한 한 적게 부수어 도로망을 다시 안전하게 만들어라. 도로 조각 하나를 부순다는 것은 그 칸의 문자를 .(점)으로 바꾸는 것이다.

첫째 줄에 도로망의 행 수 $R$과 열 수 $S$가 주어진다. $1 \le R \le 20$, $1 \le S \le 20$이다.

다음 $R$개 줄에는 각각 $S$개의 문자가 주어진다. 문자는 문제에서 설명한 방식으로 도로망을 나타내며, 위에 적은 6가지 문자만 나온다.

안전하게 고친 도로망을 $R$개 줄에 각각 $S$개 문자로 출력한다. 원래 도로망에서 도로 조각을 .(점)으로 바꾸는 것 말고 다른 변경은 하면 안 된다.

부순 도로 조각의 개수가 최소인 안전한 도로망은 유일함을 증명할 수 있다.