#MA0701. 移棋子游戏

移棋子游戏

问题描述

有个 n×mn×m 的棋盘,其中 (1,1)(1,1) 格在左上角,(n,m)(n,m) 格在右下角。棋盘的第一行和第一列的每个格子标了黑白两种颜色。

上面有一个棋子。AliceBob 轮流移动这个棋子,Alice 先手移动。每次可以往上或往左移动一格,一旦这个棋子移动到第一行或者第一列游戏结束。执行最后一步移动的人,如果将棋子移动到黑格,那么就获胜,否则就失败。

现在给这个棋子的起始位置,问最后获胜的玩家是谁,对于所有 (i,j)(i,j) 满足 2in,2jm2≤i≤n,2≤j≤m 输出。

输入格式

第一行两个整数 n,m(2n,m1000)n,m(2≤n,m≤1000)

接下来一行 m1m−1 个由 BW 构成的字符串,分别表示第一行 22mm 格的颜色,其中B是黑色,W是白色。

接下来一行 n1n-1 个由 BW 构成的字符串,分别表示第一列 22nn 格的颜色,其中 B 是黑色,W 是白色。

输出格式

一共 n1n-1 行,每行 m1m−1 个字母,表示胜者。如果 Alice 获胜,输出一个 A,否则输出一个 B

样例

3 4
WBW
BW
AAB
BAA

样例说明

评测用例规模与约定