RPG 메이커

RPG의 맵을 만들려고 한다. 맵은 $H$행 $W$열의 격자이고, 각 칸에는 다음 네 기호 중 하나가 들어간다.

• @: 시작 칸. 이야기는 이 칸에서 시작한다.
• *: 도시 칸. 이야기는 이 칸을 지나가거나 이 칸에서 끝난다.
• #: 길 칸.
• .: 빈 칸.

시작 칸과 모든 도시 칸은 입력 조건에 맞게 이미 놓여 있고, 길 칸은 아직 하나도 놓이지 않았다. 어떤 빈 칸을 길 칸으로 바꿀지 정해야 한다.

맵에는 여정이 하나 있어야 한다. 이야기가 갈라지면 안 되므로 여정도 갈라지면 안 된다. 여정은 다음 조건을 모두 만족하는 칸의 나열이다.

1. 여정에 들어가는 도시 칸의 개수가 최대이다.
2. 여정은 빈 칸이 아닌 서로 다른 칸으로만 이루어진다.
3. 여정은 시작 칸에서 시작한다.
4. 여정은 도시 칸에서 끝난다.
5. 모든 길 칸이 여정에 들어간다. 여정 밖에 놓인 길 칸은 없다.
6. 여정의 첫 칸과 마지막 칸을 뺀 나머지 칸은 여정에 속한 칸과 변을 정확히 두 개 맞댄다. 첫 칸과 마지막 칸은 여정에 속한 칸과 변을 정확히 하나 맞댄다.
7. 도시를 방문하는 순서는 상관없다.

빈 칸은 몇 개든 길 칸으로 바꿀 수 있다. 완성한 맵을 출력한다.

입력은 다음 형식의 테스트 케이스 하나로 주어진다.

H W
S1
S2
...
SH

첫 줄에 정수 $H$와 $W$가 주어진다. $H = 4n - 1$, $W = 4m - 1$을 만족하는 양의 정수 $n$과 $m$이 있으며, $1 \le n, m \le 10$이다. 이어지는 $H$개의 줄은 길 칸이 없는 맵이다. $i+1$번째 줄은 길이가 $W$인 문자열 $S_i$이다. $S_i$의 $j$번째 문자는 $i$와 $j$가 모두 홀수이면 *, @, . 중 하나이고, 그렇지 않으면 .이다. 격자에 @는 정확히 하나 있고, 도시 칸은 하나 이상 있다.

조건을 만족하는 맵은 여러 개일 수 있으므로, 아래 방법으로 만든 맵만 정답으로 인정한다.

행은 위에서부터 $1$번부터 $H$번까지, 열은 왼쪽에서부터 $1$번부터 $W$번까지 번호를 매긴다. 행 번호와 열 번호가 모두 홀수인 칸을 정점이라고 부르고, $2i+1$행 $2j+1$열의 칸을 정점 $(i, j)$라고 쓴다. 여기서 $0 \le i < 2n$이고 $0 \le j < 2m$이다. 두 정점의 좌표가 한쪽에서만 $1$ 차이 나면 두 정점은 서로 이웃이고, 그 사이에 있는 칸 하나가 두 정점을 잇는 칸이다.

정점 $4nm$개를 한 번씩 지나는 순환 $C$를 다음 순서로 적는다.

1. $(0, 0), (0, 1), \ldots, (0, 2m-1)$
2. 이어서 $i = 1$부터 $i = 2n-1$까지 차례로, $i$가 홀수면 $(i, 2m-1), (i, 2m-2), \ldots, (i, 1)$을, $i$가 짝수면 $(i, 1), (i, 2), \ldots, (i, 2m-1)$을 적는다.
3. 이어서 $(2n-1, 0)$
4. 이어서 $(2n-2, 0), (2n-3, 0), \ldots, (1, 0)$

$C$에서 연달아 적힌 두 정점은 실제로 이웃이고, 마지막 정점 $(1, 0)$과 첫 정점 $(0, 0)$도 이웃이다.

@가 있는 정점에서 출발해 $C$에 적힌 순서대로 나아간다. 끝에 닿으면 처음으로 돌아가고, 정점 $4nm$개를 모두 한 번씩 지나면 멈춘다. 이렇게 얻은 나열을 마지막 도시 정점 바로 뒤에서 자른다. 남은 정점과 연달아 놓인 두 정점을 잇는 칸이 여정이다.

$H$개의 줄에 맵을 출력한다. 여정에 속한 칸 중 입력에서 빈 칸이었던 칸은 #로 바꾸고, 나머지 칸은 입력 그대로 둔다. 이 방법으로 만든 여정은 도시 칸을 모두 지난다.