좌석 배정 알고리즘

저가 항공사가 표를 먼저 산 승객에게 더 좋은 좌석을 주는 배정 알고리즘을 만들고 있다. 비행기에는 좌석 열이 $r$개 있고 $r$는 짝수다. 좌석이 없고 비상구로만 이어지는 비상구 열도 3개 있다. 하나는 맨 앞(첫 좌석 열 바로 앞), 하나는 맨 뒤(마지막 좌석 열 바로 뒤), 나머지 하나는 정확히 가운데에 있다. 열 번호는 앞에서 뒤로 가면서 1부터 $r + 3$까지 붙는다. 번호가 $1$, $r/2 + 2$, $r + 3$인 열이 비상구 열이고 나머지는 모두 좌석 열이다.

좌석 배치는 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인 좌석 전부다. 빈 좌석이 더 많은 쪽의 좌석을 고른다. 양쪽의 빈 좌석 수가 같으면 왼쪽 좌석을 고른다.

비행기의 일부 좌석은 이미 예약되어 있고, 그 예약 절차는 위 절차와 전혀 다를 수도 있다. 다음으로 표를 사는 승객 $n$명에게 배정되는 좌석을 구하라.

첫째 줄에 정수 $r$와 $n$이 주어진다 ($2 \le r \le 50$, $1 \le n \le 26$). $r$는 비행기의 좌석 열 개수이고 항상 짝수다. $n$은 새로 표를 사는 승객 수다. 다음 $r + 3$개 줄에는 비행기의 현재 배치가 주어진다. 그중 $j$번째 줄은 정확히 11개 문자로 이루어지고 $j$번 열의 배치를 나타낸다. 비상구 열과 통로는 . 문자로 나타낸다. #는 이미 예약된 좌석이고 -는 빈 좌석이다. 비행기에는 빈 좌석이 $n$개 이상 있다.

비행기의 최종 배치를 $r + 3$개 줄에 출력한다. 배치는 입력과 같고, $j$번째 승객에게 배정된 좌석만 알파벳 소문자의 $j$번째 글자로 나타낸다.