单人国际象棋（Chess Solitaire）是一种适合单人游玩的国际象棋变体。当然，你可能已经自己想到了，但具体规则如下：给定一个摆放了 2 个或更多棋子（其中没有兵（pawn））的棋盘，找到一系列吃子（捕获）步骤，使得最后棋盘上只剩下一个棋子。每次移动棋子都必须吃掉另一个棋子，因此如果初始时棋盘上有 $m$ 个棋子，那么解法将包含 $m-1$ 步移动。图 1 展示了一个谜题示例及其解法（对应样例输入 1）：

图 1：单人国际象棋谜题及其解法。

温馨提示，以下是各种棋子吃子（捕获）的规则：

• 国王 (K)：可以向周围八个方向（横、竖、斜）移动一格。
• 皇后 (Q)：可以向八个方向（横、竖、斜）移动任意格，但不能越过其他棋子。
• 主教 (B)：可以向四个斜向方向移动任意格，但不能越过其他棋子。
• 战车 (R)：可以向四个直向（横、竖）方向移动任意格，但不能越过其他棋子。
• 骑士 (N)：可以向一个直向移动两格，再向垂直方向移动一格（即走“日”字），且可以越过其他棋子。

棋子移动与吃子规则

对于本题，你将获得一个单人国际象棋谜题，并需要输出解决该谜题的一系列步骤。

输入格式

输入以一行 $n$ $m$ 开始，其中 $n$ ($2 \le n \le 8$) 表示棋盘的行数和列数，$m$ ($2 \le m \le 10$) 表示谜题中的棋子数量。

接下来的 $m$ 行，每行格式为 $p$ $loc$，其中 $p$ 是 'N'、'B'、'R'、'Q'、'K' 之一，分别代表骑士、主教、战车、皇后和国王；$loc$ 是一个长度为 2 的字符串，表示棋子在棋盘上的位置。

$loc$ 的第一个字符是一个大写字母，表示行；第二个字符是一个整数，表示列（如上图所示）。所有位置均合法，且任意两个棋子的初始位置不相同。

输出格式

输出 $m-1$ 行，展示解决该谜题所需的 $m-1$ 步移动。每行的格式应为 p: loc1 -> loc2，表示将棋子 $p$ 从位置 $loc_1$ 移动到位置 $loc_2$。

若有多种解法，输出第一步移动中 $loc_1$ 字典序最小的解。如果仍有并列，则输出第一步移动中 $loc_2$ 字典序最小的解。如果仍有并列，则将这些规则依次应用于第二步移动，以此类推。

若谜题无解，输出 No solution。

样例

输入样例 1

5 5
N E3
Q C1
R C2
B C4
R A3

输出样例 1

Q: C1 -> A3
R: C2 -> C4
N: E3 -> C4
N: C4 -> A3

输入样例 2

4 4
Q D4
Q B1
Q C2
K A3

输出样例 2

No solution