Seat Assignment Algorithm

A low cost airline is building an assignment algorithm that gives better seats to passengers who buy their tickets earlier. The airplane has $r$ rows of seats, and $r$ is even. It also has 3 exit rows, which hold no seats and only give access to the emergency exits. One exit row is at the very front of the airplane, right before the first row of seats. One is at the very back, right behind the last row of seats. The third one is exactly in the middle. The rows are numbered with integers 1 through $r + 3$, increasing from the front to the back of the airplane. Rows $1$, $r/2 + 2$ and $r + 3$ are exit rows, and every other row is a seat row.

The seating configuration is 3-3-3. Each seat row holds three groups of three seats, with the passenger aisles between the groups. Seats in the same row are named with consecutive letters from left to right, following the pattern ABC.DEF.GHI.

When a passenger buys a ticket, the airline assigns a seat by the following rules.

1. If a row directly after an exit row has an empty seat, every other row is ignored in the next step. Those rows still count when the balance of the airplane is measured in the last step.

2. First, select the seat row with the largest number of empty seats. If several rows tie, select the one closest to an exit row. The distance between rows $a$ and $b$ is $|a - b|$. If several rows still tie, select the one with the lowest number.

3. Among the empty seats of the selected row, select the one with the highest priority. The priorities, from highest to lowest, are:

   1. aisle seats in the middle group (D or F)
   2. aisle seats in the first and the third group (C or G)
   3. window seats (A or I)
   4. the middle seat of the middle group (E)
   5. the other middle seats (B or H)

   If two empty seats share the highest priority, the balance of the whole airplane decides. The left side holds every seat whose letter is A, B, C or D, and the right side holds every seat whose letter is F, G, H or I. Select the empty seat on the side with more empty seats. If both sides have the same number of empty seats, select the seat on the left side.

Some seats of the airplane are already reserved, possibly by a procedure completely different from the one above. Determine the seats assigned to the next $n$ passengers who buy a ticket.

The first line contains two integers $r$ and $n$ ($2 \le r \le 50$, $1 \le n \le 26$). $r$ is the number of seat rows in the airplane and is always even. $n$ is the number of new passengers who buy a ticket. The following $r + 3$ lines contain the current layout of the airplane. The $j$-th of those lines contains exactly 11 characters and describes row $j$. Exit rows and aisles are written with the . character. The # character marks a reserved seat, and the - character marks an empty seat. The airplane has at least $n$ empty seats.

Print the final layout of the airplane on $r + 3$ lines. The layout is the same as the one in the input, except that the seat assigned to the $j$-th passenger is written with the $j$-th lowercase letter of the English alphabet.