5.黑白棋

题目描述

有一个双人游戏，规则如下：

有一个$1 \times N$的棋盘。

初始时，上面有若干个黑或白的棋子。任意时刻，每个棋子位于一个格子内，每个格子中最多有一个棋子。所有白棋均在所有黑棋左侧。双方轮流操作，白方先手。

白方的回合中，白方选择一个白棋向右移动一格。在黑方的回合中，黑方选择一个黑棋向左移动一格。不允许将棋子移动到已经被同色棋子占据的格子中。如果移动到的格子内有一个异色棋子，则将异色棋子移出游戏。不可操作者，也就是棋子全被移出游戏者，输，另一方赢。

有$T$个初始局面，你需要求出双方都采取最优决策的情况下，哪一方获胜。

输入格式

第一行一个正整数$T$，表示数据组数。

接下来$T$行，每行一个字符串$S$，代表初始棋盘，$W$表示白棋，$B$表示黑棋，$.$代表空位。

输出格式

$T$行，每行一个字符$W$或$B$，表示双方均采取最优策略时获胜方为白方还是黑方。

数据范围与提示

对于$100\%$的数据，$\sum n \leq 10^{5}$，保证$S$中存在至少一个$W$与至少一个$B$，最右的$W$在最左的$B$的左侧。

样例

2
W..B
WW.B

W
B

10
W.W..W.W..B
WBBB..BB.
.WWW.B..B.B.
....WWW.B
.WWWWWWWW.WWWB
WWBBB.
WWWWW..WWB.
.WW.WWW.BBB
WWBB......B.B
.WBBB.B.

W
B
B
B
W
B
W
W
B
B