题目描述

A low-budget airline is designing a sophisticated algorithm that will assign more desirable seats to passengers who buy tickets earlier. Their airplane has $r$ rows of seats, where $r$ is an even integer. There are also $3$ exit rows in the airplane; those rows do not contain any seats but only provide access to the emergency exits. One exit row is in the very front of the airplane (before the first row of seats), one in the very back (behind the last row of seats) and one right in the middle. The rows are numbered with integers $1$ through $r + 3$ with row numbers increasing from the front to the back of the airplane. Rows numbered $1$, $r/2 + 2$ and $r + 3$ are exit rows while all the other rows are seat rows. The seating configuration is “3–3–3” — each seat row contains three groups of three seats with the passenger aisles between the groups. Seats in the same row are denoted with consecutive letters left to right corresponding to the pattern “ABC.DEF.GHI”. When a passenger purchases a ticket, she is assigned a seat according to the following rules:

1. If there is an empty seat in a row directly after an exit row, all other rows are ignored in the following step (but they are not ignored when balancing the airplane in the last step).
2. First, we select a seat row with the largest number of empty seats. If there are multiple such rows,we select the one closest to an exit row (distance between rows $a$ and $b$ is simply $|a − b|$). If there are still multiple such rows, we select the one with the lowest number.
3. Now, we consider empty seats in the selected row and select one with the highest priority. Seat priorities, from highest to lowest are as follows:

• (a) Aisle seats in the middle group (D or F).
• (b) Aisle seats in the first and third group (C or G).
• (c) Window seats (A or I).
• (d) Middle seat in the middle group (E).
• (e) Other middle seats (B or H).

If there are two empty seats with the same highest priority, we consider the balance of the entire airplane. The airplane’s left side contains all seats with letters A, B, C or D, while the right side contains all seats with letters F, G, H or I. We select an empty seat in the side with more empty seats. If both sides have the same number of empty seats, we select the seat in the left side of the airplane.

Some of the airplane’s seats are already reserved (possibly using a completely different procedure from the one described above). Determine the seats assigned to the next $n$ passengers purchasing a ticket.

输入格式

The first line contains two integers $r$ and $n(2 \le r \le 50, 1 \le n \le 26)$ — the number of seat rows in the airplane (always an even integer) and the number of new passengers purchasing tickets. The following $r + 3$ lines contain the current layout of the airplane. The $j-th$ line contains exactly $11$ characters — the layout of the row $j$ of the airplane. Exit rows and aisles are denoted with the “.” characters. The “#” character denotes a reserved seat, while the “-” character denotes a seat that is currently empty. You may assume there will be at least $n$ empty seats in the airplane.

输出格式

Output $r + 3$ lines containing the final layout of the airplane. The layout should be exactly the same as in input with the following exception: the seat assigned to the $j-th$ passenger purchasing a ticket should be denoted with the $j-th$ lowercase letter of the English alphabet.

题目大意

题目描述

一家航空公司正在设计一种复杂的算法，将为提前购票的乘客分配更理想的座位。他们的飞机有 $r$ 排座位，其中 $r$ 是一个偶数。飞机上有 $3$ 行出口行，这些排没有座位，只提供通往紧急出口的通道。一个出口排在飞机的最前面（在第一排座椅之前），一个在最后面（在最后一排座椅之后），另一个在中间的位置。这些行用整数 $1$ 到 $r+3$ 进行编号，行号从飞机前部到后部递增。

编号为 $1$、$r/2+2$ 和 $r+3$ 的行是出口行，而所有其他行都是座位行。 座位配置为 “$3–3–3$” 每排座位包含三个组三个座位，每组座位之间有乘客通道。同一排座位用从左到右的连续字母表示，对应于“ABC.DEF.GHI”模式。 当乘客购买机票时，会根据以下规则为其分配座位：

1.如果在出口排的正后方有一排空座位，则在接下来的步骤中忽略所有其他排（但在最后一步中平衡飞机时不忽略）。

2.首先，我们选择空座位数最多的一排座位。如果有多个这样的行，则选择最靠近出口行的行（行 $a$ 和 $b$ 之间的距离仅为 $|a− b|$）。如果仍有多个这样的行，则选择编号最低的行。

3.现在，我们考虑所选行中的空座位，并选择一个优先级最高的座位。座位优先级从高到低排序按照如下规则：
-（a）中间组的过道座位（即D或F）。
-（b）第一组和第三组的过道座位（即C或G）。
-（c）靠窗座位（即A或I）。
-（d）中间组中的中间座位（即E）。
-（e）第一组和第三组的中间座位（即B或H）。
如果有两个空座位具有相同的最高优先级，我们会考虑整个飞机的平衡。飞机左侧包含字母A、B、C或D的所有座位，而右侧包含字母F 、G、H或 I 的所有座位。我们在空座位较多的一侧选择一个空座位。如果两边有相同数量的空座位，则优先选择飞机左侧的座位。
飞机的一些座位已经预定好了（即输入中的 #）。现在请你确定分配给第 $i$ 个购票的乘客的座位。

输入格式

第一行包含两个整数 $r$ 和 $n$ （$2\le r \le50，1\le n \le26$）表示飞机中的座位排数（保证为偶数）和购买机票的乘客数。第 $2$ 到 $r+3$ 行包含飞机的当前布局。第 $j$ 行正好包含 $11$ 个字符，即飞机第 $j$ 行的布局。出口行和通道用 “.” 字符表示。“#” 字符表示已经预定好的座位，而“-”表示当前空座位。保证飞机上至少有 $n$ 个空座位。

输出格式

输出包含飞机最终布局的 $r+3$ 行。整体布局应与输入中的布局相同，分配给第 $j$ 个购票乘客的座位应使用英文字母，依次从小写字母 $a$ 到 $z$ 表示。

样例输入 #1.

2 17
...........
---.#--.---
...........
---.---.---
...........

样例输出 #1

...........
hnd.#lb.fpj
...........
kqg.cma.eoi
...........

样例输入 #2

6 26
...........
---.---.###
#-#.---.---
---.###.---
...........
---.###.---
#--.#-#.--#
#--.--#.#-#
...........

样例输出 #2

...........
gke.aic.###
#-#.mzo.r-v
x-p.###.n-t
...........
fjb.###.dlh
#-s.#-#.w-#
#-u.qy#.#-#
...........

2 17
...........
---.#--.---
...........
---.---.---
...........

...........
hnd.#lb.fpj
...........
kqg.cma.eoi
...........

6 26
...........
---.---.###
#-#.---.---
---.###.---
...........
---.###.---
#--.#-#.--#
#--.--#.#-#
...........

...........
gke.aic.###
#-#.mzo.r-v
x-p.###.n-t
...........
fjb.###.dlh
#-s.#-#.w-#
#-u.qy#.#-#
...........