Description

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

Input Format

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

Output Format

输出包含飞机最终布局的 $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#.#-#
...........