밭에 물 주기

사라는 큰 직사각형 땅에서 농사를 짓는다. 땅은 $5R$개의 행과 $5C$개의 열로 이루어진 격자이고, 다섯 행마다 가로 울타리가, 다섯 열마다 세로 울타리가 놓여 있다. 울타리는 땅을 $5 \times 5$ 크기의 구역 $R \times C$개로 나눈다. 이 구역 하나를 밭이라고 한다.

새를 쫓으려고 일부 밭에는 허수아비가 서 있다. 허수아비는 한 칸을 차지하고, 한 밭에 많아야 하나 있다.

스프링클러 하나에는 분사구가 셋 달려 있다. 가운데 분사구 하나와 옆 분사구 둘인데, 옆 분사구 둘은 가운데 분사구의 칸과 변을 맞댄 서로 다른 두 칸에 놓인다. 그래서 스프링클러 하나는 정확히 세 칸을 차지하고 그 세 칸에 물을 준다. 모양은 가로 일자, 세로 일자, 그리고 방향이 다른 ㄱ자 넷을 합쳐 여섯 가지다.

사라는 허수아비가 없는 모든 칸이 정확히 한 스프링클러의 물을 받도록 배치하려고 한다. 허수아비가 있는 칸에는 분사구를 놓을 수 없고, 분사구가 땅 밖으로 나가서도 안 된다.

한 스프링클러가 물을 주는 세 칸이 같은 밭에 있을 필요는 없다. 이웃한 밭에 걸쳐도 되며, 그때는 같은 스프링클러가 물을 주면서 서로 다른 밭에 있는 두 칸 사이의 울타리에 구멍을 뚫어야 한다.

땅의 상태가 주어진다. 출력 규칙이 정하는 배치를 구하라.

첫 줄에 두 정수 $R$과 $C$가 주어진다 ($1 \le R, C \le 100$).

다음 $6R-1$개의 줄에는 각각 $6C-1$개의 문자가 있다. 밭과 그 사이의 울타리를 나타내며, 울타리는 두께가 없지만 문자로 적는다.

칸 하나는 문자 하나다. .은 빈 칸, #은 허수아비가 있는 칸이다. 세로 울타리는 |, 가로 울타리는 -, 울타리가 만나는 자리는 +이다.

허수아비가 없는 밭의 개수는 3의 배수다. 따라서 올바른 배치는 항상 존재한다.

입력과 같은 형식으로 배치를 출력한다. 울타리에 뚫은 구멍은 _로 적고, 빈 칸 .은 모두 a부터 z까지의 소문자로 바꾼다. 올바른 배치는 다음을 만족한다.

1. 한 스프링클러가 물을 주는 세 칸은 같은 밭에 있지 않더라도 같은 글자로 적는다.
2. 같은 밭에서 변을 맞댄 두 칸이 서로 다른 스프링클러의 물을 받으면 두 글자는 달라야 한다.
3. 서로 다른 밭에 있는 두 칸이 변을 맞대고, 그 사이 울타리에 구멍이 있고, 서로 다른 스프링클러의 물을 받으면 두 글자는 달라야 한다.
4. 서로 다른 밭에 있는 이웃한 두 칸은 위 조건을 어기지 않는 한 같은 글자여도 된다.

올바른 배치는 여럿일 수 있다. 다음 규칙이 정하는 배치 하나만 정답으로 인정한다.

1. 밭에 번호를 매긴다. 첫 밭 행은 왼쪽에서 오른쪽으로, 다음 밭 행은 오른쪽에서 왼쪽으로, 이렇게 방향을 번갈아 가며 $1$번부터 $R \times C$번까지 매긴다.
2. 허수아비가 없는 밭을 이 번호 순으로 늘어놓고 앞에서부터 셋씩 묶는다. 한 묶음의 번호를 $a < b < c$라고 하자.
3. 각 묶음마다, $a \le t < c$인 모든 $t$에 대해 $t$번 밭과 $t+1$번 밭 사이의 울타리를 지나는 스프링클러가 정확히 하나 있다. 그 밖의 울타리를 지나는 스프링클러는 없다.
4. $a \le t < b$이면 그 스프링클러는 $t$번 밭에서 한 칸, $t+1$번 밭에서 두 칸을 차지한다. $b \le t < c$이면 $t$번 밭에서 두 칸, $t+1$번 밭에서 한 칸을 차지한다.
5. 울타리를 지나는 스프링클러는 모두 일자다. 세로 울타리를 지나면 땅의 한 행에, 가로 울타리를 지나면 땅의 한 열에 놓인다. 두 칸을 차지하는 쪽에서는 울타리에서 가장 가까운 두 칸을 차지한다. 그 행이 밭의 다섯 행 중 몇 번째인지, 또는 그 열이 밭의 다섯 열 중 몇 번째인지를 그 울타리의 트랙이라고 하자. 트랙은 $1$부터 $5$까지의 수다.
6. 모든 밭에서 허수아비 칸과 울타리를 지나는 스프링클러가 차지한 칸을 뺀 나머지를 그 밭 안에 완전히 들어가는 스프링클러로 덮을 수 있도록 트랙을 정한다. 그런 선택이 여럿이면, 울타리를 번호 순으로 늘어놓았을 때 트랙 수열이 사전순으로 가장 앞서는 것을 고른다. 그런 선택은 항상 존재한다.
7. 각 밭의 나머지 칸은 다음을 되풀이해 덮는다. 아직 덮이지 않은 칸을 행이 작은 것부터, 행이 같으면 열이 작은 것부터 늘어놓고 첫 칸을 고른다. 그 칸을 덮으면서 밭 안에 완전히 들어가고, 아직 덮이지 않은 칸만 차지하고, 그 밭의 남은 칸을 끝까지 덮을 수 있게 남기는 스프링클러 중에서, 세 칸을 같은 순서로 정렬한 목록이 사전순으로 가장 앞서는 것을 놓는다.
8. 한 스프링클러가 차지하는 두 칸이 서로 다른 밭에 있고 변을 맞댄 자리마다 울타리에 구멍을 하나 뚫는다. 나머지 울타리 문자는 입력과 같다.
9. 모든 스프링클러를, 그 스프링클러가 차지하는 칸 중 행이 작은 것부터, 행이 같으면 열이 작은 것부터 따져 첫 번째인 칸의 순서로 줄 세운다. 그 순서대로 각 스프링클러에 글자를 준다. 같은 밭 안에서 이 스프링클러의 칸과 변을 맞댄 칸을 가진 앞선 스프링클러가 이미 쓴 글자를 뺀 다음, a부터 z까지 중 가장 앞선 글자를 준다.