一家廉价航空公司正在设计一种复杂的算法，为更早购票的乘客分配更理想的座位。他们的飞机有 $r$ 排座位，其中 $r$ 是一个偶数。飞机上还有 3 排出口行；这些行不包含任何座位，仅提供通往紧急出口的通道。一排出口行位于飞机的最前端（第一排座位之前），一排位于最后端（最后一排座位之后），还有一排位于正中间。行号用整数 $1$ 到 $r + 3$ 表示，行号从飞机前部向后部递增。编号为 $1$、$r/2 + 2$ 和 $r + 3$ 的行是出口行，而所有其他行都是座位行。
座位布局为“3–3–3”——每排座位包含三组三个座位，组与组之间有乘客过道。同一排的座位从左到右用连续的字母表示，对应模式“ABC.DEF.GHI”。
当乘客购买机票时，系统会根据以下规则为其分配座位：
- 如果出口行之后紧邻的行中有空座位，则在接下来的步骤中忽略所有其他行（但在最后一步平衡飞机时不会忽略它们）。
- 首先，我们选择空座位数量最多的座位行。如果存在多个这样的行，我们选择距离出口行最近的一行（行 $a$ 和 $b$ 之间的距离简单地为 $|a - b|$）。如果仍然存在多个这样的行，我们选择行号最小的一行。
- 现在，我们考虑所选行中的空座位，并选择优先级最高的一个。座位优先级从高到低依次为： (a) 中间组的过道座位（D 或 F）。 (b) 第一组和第三组的过道座位（C 或 G）。 (c) 靠窗座位（A 或 I）。 (d) 中间组的中间座位（E）。 (e) 其他中间座位（B 或 H）。
如果存在两个优先级相同的最高优先级空座位，我们考虑整架飞机的平衡。飞机的左侧包含所有字母为 A、B、C 或 D 的座位，而右侧包含所有字母为 F、G、H 或 I 的座位。我们选择空座位较多一侧的空座位。如果两侧的空座位数量相同，我们选择飞机左侧的座位。
飞机上的一些座位已经被预订（可能使用了与上述完全不同的程序）。请确定分配给接下来 $n$ 位购票乘客的座位。
输入格式
第一行包含两个整数 $r$ 和 $n$ ($2 \le r \le 50, 1 \le n \le 26$)，分别表示飞机上的座位行数（始终为偶数）和购买机票的新乘客人数。接下来的 $r + 3$ 行包含飞机的当前布局。第 $j$ 行包含恰好 11 个字符，表示飞机第 $j$ 行的布局。出口行和过道用“.”字符表示。“#”字符表示已预订的座位，而“-”字符表示当前为空的座位。你可以假设飞机上至少有 $n$ 个空座位。
输出格式
输出 $r + 3$ 行，包含飞机的最终布局。布局应与输入完全相同，但有一个例外：分配给第 $j$ 位购票乘客的座位应标记为英语字母表中的第 $j$ 个小写字母。
样例
样例输入 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#.#-# ...........