Airplane Seat Assignment

Croatia Airlines, a national treasure, is investing billions of euros in a sophisticated algorithm that assigns better airplane seats to passengers who bought their tickets earlier.

The seats span $r$ rows, where $r$ is even. There are three exit rows with no seats. The first exit row is at the very front of the plane (before the first seat row), the second is exactly in the middle, and the third is at the very back (after the last seat row). Rows are numbered with natural numbers from $1$ to $r+3$ from the front to the back. So rows $1$, $r/2+2$, and $r+3$ are exit rows, and every other row has seats.

The seat layout is 3-3-3. Each seat row has three groups of three seats, with an aisle between groups. Seats in each row are labeled with consecutive letters from left to right as ABC.DEF.GHI.

When a passenger buys a ticket, the algorithm assigns a seat by these rules:

1. If a row directly behind an exit row has at least one empty seat, the rules below ignore all other rows that do not satisfy this condition.
2. Pick the row with the most empty seats. If several rows tie, pick the row closest to an exit row, where the distance between rows $a$ and $b$ is $|a-b|$. If there is still a tie, pick the row with the smallest number.
3. Consider all empty seats in the chosen row and pick the one with the highest priority. The priority order from highest to lowest is:
   1. Seats next to the aisle in the middle group (D and F)
   2. Seats next to the aisle in the first and third groups (C and G)
   3. Window seats (A and I)
   4. Middle seat of the middle group (E)
   5. The remaining middle seats (B and H)

If two or more empty seats share the highest priority, consider the balance of the whole plane. Passengers on the left side sit in seats A, B, C, and D, and passengers on the right side sit in seats F, G, H, and I. The algorithm picks a seat on the side with more empty seats. If both sides have the same number of empty seats, it picks a seat on the left side.

The first line contains natural numbers $r$ and $n$ ($2 \le r \le 50$, $1 \le n \le 26$). The next $r+3$ lines describe the current seat state. Each line has exactly 11 characters. Exit rows and aisles are marked with '.', reserved seats with '#', and empty seats with '-'.

You may assume that the plane has at least $n$ empty seats.

Print $r+3$ lines showing the seat state after assigning seats to the next $n$ passengers. The format is the same as the input, except that the seat assigned to passenger $j$ is marked with the $j$-th lowercase letter of the English alphabet.