비행기 좌석 배정 알고리즘

우리의 자랑인 Croatia Airlines는 수십억 유로를 투자해, 먼저 항공권을 구매한 승객에게 더 좋은 좌석을 배정하는 정교한 알고리즘을 만들고 있다.

좌석은 $r$개의 행에 걸쳐 있으며, $r$은 짝수이다. 좌석이 없는 비상구 행이 세 개 있다. 첫 번째 비상구 행은 비행기의 맨 앞(첫 좌석 행 앞)에, 두 번째 비상구 행은 정확히 비행기의 중간에, 세 번째 비상구 행은 맨 뒤(마지막 좌석 행 뒤)에 있다. 행은 앞에서 뒤로 1부터 $r+3$까지 자연수로 번호가 매겨진다. 따라서 $1$번, $r/2+2$번, $r+3$번 행이 비상구 행이고, 나머지 행에는 좌석이 있다.

좌석 배치는 3-3-3이다. 각 좌석 행은 통로를 사이에 둔 세 묶음의 좌석 세 개로 이루어진다. 좌석은 왼쪽에서 오른쪽으로 ABC.DEF.GHI와 같이 연속된 글자로 표시한다.

승객이 항공권을 구매하면 알고리즘은 다음 규칙에 따라 좌석을 배정한다.

1. 비상구 행 바로 뒤의 행에 빈 좌석이 하나라도 있으면, 이 조건을 만족하지 않는 나머지 행은 다음 규칙에서 고려하지 않는다.
2. 빈 좌석이 가장 많은 행을 고른다. 그런 행이 여러 개이면 비상구 행과 가장 가까운 행을 고른다. 두 행 $a$와 $b$ 사이의 거리는 $|a-b|$이다. 그래도 여러 개이면 번호가 가장 작은 행을 고른다.
3. 선택한 행의 빈 좌석을 모두 고려해 우선순위가 가장 높은 좌석을 고른다. 우선순위는 높은 순서대로 다음과 같다.
   1. 가운데 묶음의 통로 쪽 좌석 (D, F)
   2. 첫 번째와 세 번째 묶음의 통로 쪽 좌석 (C, G)
   3. 창가 좌석 (A, I)
   4. 가운데 묶음의 가운데 좌석 (E)
   5. 나머지 가운데 좌석 (B, H)

우선순위가 같은 빈 좌석이 두 개 이상이면 비행기 전체의 균형을 본다. 왼쪽 좌석(A, B, C, D)과 오른쪽 좌석(F, G, H, I) 중 빈 좌석이 더 많은 쪽의 좌석을 고른다. 두 쪽의 빈 좌석 수가 같으면 왼쪽 좌석을 고른다.

첫 줄에 자연수 $r$과 $n$이 주어진다 ($2 \le r \le 50$, $1 \le n \le 26$). 이어서 $r+3$개의 줄에 현재 좌석 상태가 주어진다. 각 줄은 정확히 11글자이며, 비상구 행과 통로는 '.'으로, 예약된 좌석은 '#'으로, 빈 좌석은 '-'으로 표시된다.

비행기에 빈 좌석이 적어도 $n$개 있다고 가정해도 된다.

$r+3$개의 줄에 $n$명의 승객에게 좌석을 배정한 뒤의 좌석 상태를 출력한다. 출력 형식은 입력과 같으며, $j$번째 승객에게 배정된 좌석은 $j$번째 영어 소문자로 표시한다.