题目描述

俄罗斯跳棋在一张 $8\times8$、深浅格交替的棋盘上进行。左下角是深色格，棋子只能位于深色格上。列从左到右依次标为 a～h，行从下到上依次标为 1～8，例如左下角是 a1。

白方位于棋盘下方，黑方位于棋盘上方。棋子分为普通棋子和王棋两种。白方普通棋子、王棋分别用 w、W 表示；黑方普通棋子、王棋分别用 b、B 表示。

每回合可以进行普通移动或吃子移动。如果当前玩家存在至少一种吃子移动，则本回合必须吃子，不能进行普通移动。

普通棋子的普通移动

普通棋子可以沿前方斜线移动一格，目标格必须为空。白棋向编号更大的行移动，黑棋向编号更小的行移动。

普通棋子的吃子移动

普通棋子可以沿任意一个对角方向跳过一枚相邻的对方棋子，并落到该棋子后方紧邻的空格，被跳过的棋子视为被吃掉。

落地后，如果还能继续吃子，就必须在同一回合继续吃子；如果有多种继续方式，可以任选一种。因此，一次吃子移动可能包含多次跳跃，并且每次落地后可以改变方向。

在整次移动结束前，被吃掉的棋子仍留在棋盘原位置，因此会继续阻挡路线。同一枚对方棋子在一次移动中不能被吃两次，但允许多次经过或停留在同一个空格。

升变

白方普通棋子到达第 $8$ 行、黑方普通棋子到达第 $1$ 行时，立即升变为王棋。如果普通棋子在吃子途中升变，并且升变后仍能继续吃子，就必须按照王棋的规则继续吃子。

王棋的普通移动

王棋可以沿任意一个对角方向移动任意格，但经过的所有格子和目标格都必须为空。

王棋的吃子移动

王棋沿一个对角方向完成一次跳跃时，可以：

1. 先经过零个或多个空格；
2. 跳过恰好一枚对方棋子；
3. 再经过零个或多个空格，最后停在空格上。

除被跳过的对方棋子外，这条直线上的其他经过格都必须为空。

对于一次确定的跳跃，如果跳过对方棋子后的某些可选落点能够继续吃子，那么王棋必须选择其中一个能够继续吃子的落点，并继续完成吃子移动；如果所有可选落点都不能继续吃子，则可以停在其中任意一个空格上。

与普通棋子相同，被吃掉的棋子要到整次移动结束后才从棋盘移除，同一枚棋子不能在一次移动中被吃两次。

走法表示

每种走法都从棋子的起点开始，依次列出该棋子每次落地的格子：

• 普通移动使用连字符 - 分隔，例如 a3-b4；
• 吃子移动使用冒号 : 分隔，例如 c3:e5:c7。

你需要输出当前玩家的全部合法走法，并严格按照字符串字典序从小到大排列。不同棋子的走法也放在同一个序列中排序。

输入格式

前 $8$ 行描述棋盘，每行包含 $8$ 个字符：

• 第 $1$ 行描述棋盘第 $8$ 行，从 a8 到 h8；
• 第 $2$ 行描述棋盘第 $7$ 行；
• ……
• 第 $8$ 行描述棋盘第 $1$ 行，从 a1 到 h1。

字符含义如下：

• .：空格；
• w：白方普通棋子；
• W：白方王棋；
• b：黑方普通棋子；
• B：黑方王棋。

第 $9$ 行包含 WHITE 或 BLACK，表示当前行棋方。

输出格式

第一行输出一个整数 $m$，表示合法走法数量。

接下来输出 $m$ 行，每行一个合法走法，按照字符串字典序严格递增排列。

如果没有合法走法，只输出一行 0。

样例 1

输入

.b.b.b.b
b.b.b.b.
.b.b.b.b
........
........
w.w.w.w.
.w.w.w.w
w.w.w.w.
WHITE

输出

7
a3-b4
c3-b4
c3-d4
e3-d4
e3-f4
g3-f4
g3-h4

说明

这是俄罗斯跳棋的初始局面，白方共有 $7$ 种合法普通移动。

样例 2

输入

.......B
......w.
........
........
.......W
........
...W.W..
........
BLACK

输出

2
h8:c3:e1:g3
h8:d4:g1

说明

黑方王棋必须先吃掉 g7 的白棋，然后继续吃子。第二枚被吃的棋子可以是 d2 或 f2；若选择 d2，之后还必须继续吃掉 f2。

样例 3

输入

........
........
...b....
........
...b.b..
..w.....
.....w..
........
WHITE

输出

2
c3:e5:c7
c3:e5:g3

说明

由于 c3 的白棋存在吃子移动，f2 的白棋不能进行普通移动。

样例 4

输入

........
..b.....
.w......
......B.
........
........
........
........
WHITE

输出

1
b6:d8:h4

说明

白方普通棋子跳到 d8 后立即升变为王棋，并继续按照王棋规则吃子。

数据范围与保证

• 棋盘固定为 $8\times8$；
• 棋盘字符只可能是 .、w、W、b、B；
• 所有浅色格均为空；
• 第 $8$ 行不存在白方普通棋子，第 $1$ 行不存在黑方普通棋子；
• 输入局面不保证一定能在真实对局中出现，双方棋子数也可能超过 $12$；
• 行棋方一定是 WHITE 或 BLACK。

时间与空间限制

• 时间限制：$2$ 秒；
• 空间限制：$256$ MiB。