[北京省选集训2019] 完美塔防
题目背景
小N最近喜欢玩一款塔防游戏。
题目描述
这款游戏的棋盘是一个 $n \times m$ 的网格,每个格子上会有以下类型物件:
1. A 型炮台:会向上下两个方向同时发射激光,符号为 `|`;
2. B 型炮台:会向左右两个方向同时发射激光,符号为 `-`;
3. 空地:激光穿过该物件会保持方向前进,符号为 `.`;
4. 障碍:激光到达该物件会消失,符号为 `#`;
5. 正反射镜:激光到达该物件后,会依物理定律改变方向,但仍继续前进,符号为 `\`;
6. 副反射镜:激光到达该物件后,会依物理定律改变方向,但仍继续前进,符号为 `/`;
注意激光之间可以互相穿过,但如果激光射出网格边界,也会消失。
小 N 是一个强迫症玩家,他想让每一处空地都会被至少一束激光打到,但不能让激光攻击到自己的炮台以致损坏。
小 N 可以将任意多的 A 型炮台改造成 B 型炮台,也可以把任意多的 B 型炮台改造成 A 型炮台。
你可以告诉他能否通过这些改造实现他的目标吗?
输入输出格式
输入格式
第一行一个正整数 $T$,表示数据组数。
每组数据第一行有两个正整数 $n,m$。
接下来 $n $ 行,每行一个长度为 $m$ 的字符串,表示棋盘。
输出格式
对于每组数据,若无解则输出一行 `IMPOSSIBLE`,否则输出一行 `POSSIBLE`,再输出改造后的棋盘。
如果有多组解,输出任意一个即可。
输入输出样例
输入样例 #1
3
1 3
-.-
3 4
#.##
#--#
####
4 3
.|.
-//
.-.
#\/
输出样例 #1
IMPOSSIBLE
POSSIBLE
#.##
#||#
####
POSSIBLE
.-.
|//
.-.
#\/
说明
### 数据范围:
对于$100\%$的数据:
- $1\le T \le 200$;
- $1\le n,m \le 50$。
Special Judge provided by @tiger2005.