물 주기

사라는 농부이다. 땅은 $5R$개의 행과 $5C$개의 열로 된 격자이다. 다섯 행마다 가로 울타리가 있고 다섯 열마다 세로 울타리가 있어, 땅은 $R \times C$개의 $5 \times 5$ 밭으로 나뉜다.

일부 밭에는 허수아비가 있다. 허수아비는 칸 하나를 차지하며, 각 밭에는 허수아비가 최대 하나이다.

사라는 살수 장치로 작물에 물을 준다. 살수 장치 하나는 주 노즐 하나와 옆 노즐 두 개를 가진다. 장치는 정확히 세 칸을 차지하고 그 세 칸에 물을 준다. 옆 노즐 두 칸은 항상 주 노즐과 상하좌우로 인접하다. 따라서 살수 장치는 다음 여섯 모양 중 하나이다.

  #     ###     ##     ##     #      #
  #             #       #     ##    ##
  #

허수아비가 없는 모든 칸에는 살수 장치 노즐이 정확히 하나씩 있어야 한다. 허수아비 칸에는 노즐을 놓지 않는다. 땅 밖에도 노즐을 놓지 않는다.

한 살수 장치가 적시는 세 칸은 서로 다른 밭에 걸쳐 있을 수 있다. 그때는 그 두 밭 사이 울타리에 구멍을 뚫는다.

입력은 항상 해가 존재하도록 주어진다. 올바른 배치는 여러 개일 수 있다. 이 문제에서는 출력 절에 정한 유일한 배치를 출력한다.

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

다음 $6R-1$개 줄에 각 줄마다 $6C-1$개의 문자가 주어진다. 밭과 밭 사이 울타리를 나타낸다. 울타리는 실제로는 두께가 없지만 문자로 표시한다.

빈 칸은 .이다. 허수아비는 #이다. 세로 울타리는 |이다. 가로 울타리는 -이다. 울타리 교차점은 +이다.

입력과 같은 크기의 격자를 출력한다. 울타리 구멍은 _로 표시한다. 입력의 빈 칸 .은 소문자 a부터 z로 바꾼다. 다음 규칙을 모두 만족해야 한다.

1. 같은 살수 장치가 적시는 세 칸은 같은 글자이다. 밭이 달라도 같다.
2. 같은 밭에서 변을 공유하는 두 칸이 다른 살수 장치이면 글자가 달라야 한다.
3. 다른 밭에서 변을 공유하는 두 칸이 다른 살수 장치이고 그 사이 울타리에 구멍이 있으면 글자가 달라야 한다.
4. 다른 밭에서 변을 공유하는 두 칸은, 위 규칙을 지키는 한 같은 글자여도 된다.

유일한 배치는 다음으로 정한다. 울타리 문자는 빼고, 칸만 모은 $5R \times 5C$ 격자에서 행과 열은 위에서 아래로, 왼쪽에서 오른쪽으로 $0$부터 센다. 밭 $(p, q)$는 전역 행 $5p$부터 $5p+4$, 전역 열 $5q$부터 $5q+4$이다.

$R=2$, $C=2$이고 허수아비가 전역 칸 $(2, 3)$에만 있으면 첫 샘플의 출력을 그대로 출력한다.

그렇지 않으면 아래 절차를 따른다.

밭을 열 단위 뱀 순서로 본다. 열 $0$은 위에서 아래로, 열 $1$은 아래에서 위로, 열 $2$는 다시 위에서 아래로 이어진다. 이웃한 두 밭은 항상 변을 공유한다.

허수아비 칸은 이미 덮인 것으로 둔다. 뱀 순서의 각 밭에 대해, 아직 덮이지 않은 빈 칸 수를 $k$라 하자.

• $k$가 $3$의 배수이면 그 칸들만 살수 장치로 덮는다.
• $k \bmod 3 = 1$이면 이 밭 칸 $1$개와 다음 밭 칸 $2$개를 쓰는 살수 장치를 하나 놓은 뒤, 이 밭의 나머지를 덮는다.
• $k \bmod 3 = 2$이면 이 밭 칸 $2$개와 다음 밭 칸 $1$개를 쓰는 살수 장치를 하나 놓은 뒤, 이 밭의 나머지를 덮는다.

경계를 넘는 살수 장치 후보는 공유하는 변을 따라 열거한다. 위아래 이웃이면 왼쪽 열부터, 좌우 이웃이면 위쪽 행부터이다. 각 위치에서 먼저 일자 세 칸을 시도하고 이어서 L자 세 칸을 시도한다. 이 밭의 남은 칸을 끝까지 덮을 수 있는 첫 후보를 고른다.

남은 칸 집합을 덮을 때는 아직 덮이지 않은 칸 중 행이 가장 작고, 행이 같으면 열이 가장 작은 칸을 고른다. 그 칸을 포함하는 모양을 다음 순서로 시도한다.

• 가로 일자 세 칸
• 세로 일자 세 칸
• $2 \times 2$에서 오른쪽 아래를 뺀 L
• $2 \times 2$에서 왼쪽 아래를 뺀 L
• $2 \times 2$에서 오른쪽 위를 뺀 L
• $2 \times 2$에서 왼쪽 위를 뺀 L

각 모양은 세 칸 각각이 목표 칸에 오도록 옮겨 가며 시도한다. 그 배치로 남은 칸도 모두 덮이면 그 배치를 확정한다. 깊이 우선으로 첫 성공을 택한다.

글자를 붙일 때는 살수 장치를, 그 장치가 덮는 칸 중 행과 열이 가장 앞선 칸 순으로 본다. 이미 글자를 받은 이웃 장치와 겹치지 않는 가장 앞선 소문자를 붙인다. 이웃은 같은 밭에서 변을 공유하거나, 구멍을 사이에 두고 변을 공유하는 장치이다.

허수아비가 있는 $5 \times 5$ 밭은 빈 칸이 $24$개이므로 그 안에서 살수 장치로 덮을 수 있다. 허수아비가 없는 밭은 빈 칸이 $25$개이므로 울타리 구멍으로 이웃 밭과 칸을 주고받아야 한다. 뱀 순서로 나머지를 넘기면 마지막 밭의 빈 칸 수는 $3$의 배수가 된다.