스프링클러 배치

사라는 큰 직사각형 농장을 가꾼다. 농장은 세로 $5R$칸, 가로 $5C$칸의 격자다. 다섯 번째 행마다 가로 울타리가, 다섯 번째 열마다 세로 울타리가 농장을 가로지르므로, 울타리는 농장을 $5 \times 5$ 크기의 구역 $R \times C$개로 나눈다.

새가 작물을 쪼아 먹기 때문에 일부 구역에는 허수아비가 서 있다. 허수아비는 한 칸을 차지하고, 한 구역에 서 있는 허수아비는 많아야 하나다.

가뭄이 들면 사라는 스프링클러로 작물에 물을 준다. 스프링클러 하나에는 중앙 노즐 하나와 옆 노즐 두 개가 있다. 중앙 노즐이 한 칸을 차지하고, 옆 노즐 두 개는 중앙 노즐과 위, 아래, 왼쪽, 오른쪽으로 맞닿은 서로 다른 두 칸을 차지한다. 그래서 스프링클러 하나는 세 칸을 차지하고 그 세 칸에 모두 물을 준다.

사라는 허수아비가 없는 모든 칸에 노즐이 정확히 하나씩 놓이도록 스프링클러를 배치하려고 한다. 허수아비가 있는 칸에는 노즐을 놓을 수 없고, 농장 밖에도 노즐을 놓을 수 없다.

한 스프링클러가 물을 주는 세 칸이 같은 구역에 있어야 하는 것은 아니다. 세 칸이 이웃한 구역에 걸치면 사라는 두 칸 사이의 울타리에 구멍을 뚫는다.

농장이 주어지면 스프링클러 배치를 출력하라.

첫 줄에 정수 $R$과 $C$가 주어진다 ($1 \le R, C \le 100$). 농장의 크기다.

다음 $6R-1$개 줄에는 각각 문자 $6C-1$개가 주어진다. 농장과 그 사이의 울타리를 나타낸다. 울타리는 실제로 두께가 없지만 그림에서는 문자 한 칸을 차지한다.

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

한 구역에 서 있는 허수아비는 많아야 하나다. 출력에서 설명하는 절차가 끝까지 진행되도록 입력이 주어진다.

$6R-1$개 줄에 각각 문자 $6C-1$개를 출력한다. 입력과 같은 형식으로 스프링클러를 배치한 농장을 나타낸다. 허수아비가 있는 칸은 # 그대로 두고, 빈 칸은 소문자 a부터 z까지 중 하나로 바꾸고, 구멍을 뚫은 울타리 자리는 _로 바꾼다. 배치는 다음 네 조건을 만족한다.

1. 한 스프링클러가 물을 주는 세 칸은 서로 다른 구역에 있더라도 같은 문자로 나타낸다.
2. 같은 구역에서 맞닿은 두 칸에 서로 다른 스프링클러가 물을 주면, 두 칸은 다른 문자로 나타낸다.
3. 다른 구역에서 맞닿은 두 칸에 서로 다른 스프링클러가 물을 주고 그 사이 울타리에 구멍이 뚫려 있으면, 두 칸은 다른 문자로 나타낸다.
4. 위 조건을 모두 지키면 다른 구역에서 맞닿은 두 칸을 같은 문자로 나타내도 된다.

조건을 만족하는 배치는 여러 가지일 수 있으므로, 다음 절차가 만드는 배치 하나를 출력한다. 행은 위에서부터, 열은 왼쪽에서부터 센다.

칸을 위에서 아래로, 한 행 안에서는 왼쪽에서 오른쪽으로 훑는다. 허수아비가 없고 아직 아무 스프링클러도 물을 주지 않는 칸 $(r, c)$에 이르면 그 칸에 스프링클러를 놓는다. 놓는 모양은 다음 목록에서 세 칸이 모두 농장 안에 있고, 허수아비가 없고, 아직 물을 받지 않는 첫 번째 모양이다.

1. $(r, c)$, $(r, c+1)$, $(r, c+2)$
2. $(r, c)$, $(r, c+1)$, $(r+1, c)$
3. $(r, c)$, $(r, c+1)$, $(r+1, c+1)$
4. $(r, c)$, $(r+1, c)$, $(r+1, c+1)$
5. $(r, c)$, $(r+1, c-1)$, $(r+1, c)$
6. $(r, c)$, $(r+1, c)$, $(r+2, c)$

구멍은 한 스프링클러가 물을 주는 두 칸을 가르는 울타리 자리마다 하나씩 뚫고, 나머지 울타리 자리는 그대로 둔다. 울타리가 만나는 + 자리에는 구멍을 뚫지 않는다.

스프링클러에는 놓은 순서대로 번호를 매긴다. 그 순서대로, 이미 문자를 받은 스프링클러와 위 2번 조건과 3번 조건을 어기지 않는 문자 중에서 a부터 세어 가장 앞선 문자를 각 스프링클러에 준다.