P4736 [CERC2017] Assignment Algorithm

一家航空公司正在设计一种复杂的算法，将为提前购票的乘客分配更理想的座位。他们的飞机有 $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#.#-# ........... ```