题目描述

众所周知，国科英才科创学院信奥队有着充足的经费支持，每次出去参加比赛都是选择飞机出行。这次李老师和他的学生们出去比赛当然也是选择了飞机出行。

在登机之前，都是要对座位进行选择的，选择座位自然不是乱选的。李老师通过查阅了解到大多数人都是按照以下的规则进行选择座位的。

我们假设一架飞机上总共有$r+3$排的座位，从前往后编号为$1到r+3$，其中有$3$排为安全出口通道（分别为第$1$排，第$r/2+2$排，第$r+3$排），所以这$3$排是无法坐人的。每一排都固定占有$11$个位置，其中有$9$个位置是可以坐人的，座位号从左往右为$ABC.DEF.GHI$（大写字母代表可以坐的座位，$‘.’$代表这是过道）。

大多数人会以如下的规则进行座位的选择：

1、首先是选择坐在哪一排，如果安全出口通道后面一排（第$2$排和第$r/2+3$排）还有空座位，那么就会选择这一排，如果有多种选择的话，他会优先选择空座位较多那一排；如果还是有多种选择的话，他就会选择编号较小的那一排；

2、如果安全出口通道后面一排没有空座位了，他就会选择空座位数量最多的那一排；如果有多种选择的话，他就会选择最靠近安全出口通道的那一排；如果还是有多种选择的话，他会选择编号较小的那一排；

3、选择完排之后就会开始选择座位，乘客首先会根据座位的舒适度从高到低选择座位，座位的舒适度从高到低的排行如下：

(1) 位于飞机中间且靠近过道的座位（即座位$D和F$）

(2) 位于飞机两侧且靠近过道的座位（即座位$C和G$）

(3) 位于飞机靠窗位置的座位 (即座位$A和I$）

(4) 位于飞机中间且在中间的座位 （即座位$E$）

(5) 位于飞机两侧且在中间的座位 (即座位$B和H$）

如果按照舒适度选完座位之后仍有多种选择的话，他会选择能平衡飞机重量的位置。如果已选择坐在飞机左侧的人数大于已选择坐在飞机右侧的人数的话，他就会选择坐在飞机右侧，否则他就会选择坐在飞机左侧。（飞机的左侧为第$1~5$列，右侧为第$7~11$列）。

了解了这个规则之后，李老师知道他们这次的航班的飞机上总共有$r+3$排的座位，同时也知道了一部分人选择座位的情况，现在还有$n$个人（用小写字母表示）要进行选座，这$n$个人按顺序依次选择座位（即$a$最先选择座位，依次排下去，直到最后一个人）。好奇的李老师想知道如果这$n$个人按照规则选择座位的规则进行选择座位的话，最终飞机上的座位情况会是怎么样呢？聪明的国科信奥队员能帮帮李老师吗？

输入

第一行包含一个整数$T$（$1\leq T \leq 10$，表示总共有$T$组测试样例

第二行包含了两个整数$r$($2\leq r \leq 50$)和$n$($1\leq n \leq 26$)，表示李老师所乘坐的飞机有$r+3$排座位，同时有$n$个乘客要对座位进行选择。

接下来$r+3$行，每行包含$11$个字符。

输入的字符仅包含以下3种：

$‘.’$：表示过道或者安全出口通道，这个位置无法坐人；

‘-’：表示空座位；

‘#’：表示这个座位已经被人选了，无法再选择这个座位；

数据保证输入的‘-’个数大于等于$n$。

输出

对于每组样例

第一行输出一行“Case #x:”，x表示当前为第几组样例（详细见样例）；

接下来，输出一个$(r+3)*11$的矩阵，表示最后飞机上的座位安排情况。

样例

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

Case #1:
...........
hnd.#lb.fpj
...........
kqg.cma.eoi
...........

提示：本题为大模拟类型题目，实现逻辑较为复杂，请灵活使用函数来简化操作。能力不够的同学不要写这个。