Lazors 是一款关于激光和反射的益智游戏。棋盘大小为 $N \times M$；棋盘上安装了一些激光发射器和接收器；并且在棋盘的单元格中预先放置了一些方块。游戏的目标是移动这些方块，使得所有接收器都能通过一系列可能的反射和折射接收到激光束。

发射器总是位于单元格某一侧的中心。发射出的激光束方向为对角线或反对角线方向。每个发射器可以用 4 个参数描述：$x, y, \text{from\_dir}, \text{to\_dir}$，其中 $\text{from\_dir}$ 和 $\text{to\_dir}$ 为 N、S、E 或 W 中的一个，分别代表单元格的北、南、东或西侧。前两个参数表示发射的激光束来自第 $x$ 行第 $y$ 列的单元格；后两个参数表示发射激光束的方向。

接收器也位于单元格某一侧的中心。每个接收器可以用 3 个参数描述：$x, y, \text{dir}$，其中 $\text{dir}$ 为 N、S、E 或 W 中的一个，代表单元格的北、南、东或西侧。这些参数表示接收器位于第 $x$ 行第 $y$ 列单元格的 $\text{dir}$ 侧中心。

共有 4 种类型的方块：白色方块、黑色方块、玻璃方块和棱镜方块。每种类型的方块在激光束的反射和折射方面都有其独特的性质。

白色方块根据反射定律反射激光束。

黑色方块吸收激光束。激光束在击中黑色方块后停止。

玻璃方块将一束激光分成两束，其中一束根据反射定律反射，另一束穿过方块。

棱镜方块折射激光束。激光束会“平移”一个网格单位，并保持原来的方向继续前进。

固定方块被锁定在棋盘上。你不能移动固定方块。黑色方块、玻璃方块和棱镜方块也可以是固定的。

输入格式

输入的第一行给出一个整数 $T$，表示测试用例的数量。接下来是 $T$ 个测试用例。

每个测试用例的第一行包含两个整数：$N, M$。接下来的 $N$ 行每行包含 $M$ 个字符：

• ‘.’ 表示一个空单元格。
• ‘#’ 表示一个禁止放置任何方块的单元格。
• ‘o’ 或 ‘O’ 表示一个白色方块。
• ‘b’ 或 ‘B’ 表示一个黑色方块。
• ‘x’ 或 ‘X’ 表示一个玻璃方块。
• ‘m’ 或 ‘M’ 表示一个棱镜方块。
• 大写字母表示固定的方块。

下一行包含一个整数 $X$，表示发射器的数量。接下来的 $X$ 行，每行包含 2 个整数 $x, y$ 和 2 个字符 $\text{from\_dir}, \text{to\_dir}$。

下一行包含一个整数 $Y$，表示接收器的数量。接下来的 $Y$ 行，每行包含 2 个整数 $x, y$ 和 1 个字符 $\text{dir}$。

输出格式

对于每个测试用例，输出一行 “Case #x:”，其中 $x$ 是测试用例编号（从 1 开始）。如果存在解，则打印棋盘配置，格式与输入相同；如果不存在解，则打印一行 “No solution!”。如果存在多个解，接受任何一个解。

数据范围

• $1 \le T \le 120$
• $1 \le N, M \le 6$
• $1 \le N \times M \le 24$
• $0 \le x < N$
• $0 \le y < M$
• $\text{dir}, \text{from\_dir}, \text{to\_dir}$ 为 N、S、E 或 W 中的一个
• $1 \le X \le 2$
• $1 \le Y \le 5$

样例

输入 1

3
3 3
###
#.#
##o
1
0 0 N E
1
0 2 N
3 3
#m.
.xb
o##
2
0 0 N E
0 2 E S
2
1 0 W
2 0 W
4 4
o.bo
obBo
b.b.
Bb..
1
0 1 N E
1
2 3 E

输出 1

Case #1:
###
#o#
##.
Case #2:
#xb
..o
m##
Case #3:
b.ob
o.Bo
b...
Bbob

说明

Case #1:

Case #2:

Case #3: