题目描述

Alice 和 Bob 在一个网格上进行追逐游戏。部分格子是墙，其余格子可以通行。所有可通行格子按照四联通关系构成一棵树：任意两个可通行格子之间都恰好只有一条简单路径。

Alice 和 Bob 各有一个棋子，初始位置分别由字符 A 和 B 给出。Alice 先手，两人轮流行动；每次行动都必须把自己的棋子移动到一个相邻的可通行格子。如果任意时刻两个棋子位于同一格，Alice 立即获胜。如果 Bob 能够成功完成 $100000$ 次移动，则 Bob 获胜。

棋盘完全处于黑暗中。Alice 和 Bob 都知道双方的初始位置，但 Alice 在游戏过程中无法得知 Bob 的移动。Bob 则拥有特殊能力：在游戏开始前，他可以准确预知 Alice 之后的完整移动序列，并据此制定自己的策略。

判断双方均采用最优策略时谁会获胜。

输入格式

第一行输入两个整数 $H,W$，表示网格的行数和列数。

接下来 $H$ 行，每行一个长度为 $W$ 的字符串，字符含义如下：

• #：墙；
• .：空地；
• A：Alice 的初始位置；
• B：Bob 的初始位置。

输出格式

如果 Alice 必胜，输出：

Alice wins

否则输出：

Bob wins

数据范围

• $2\le H,W\le 50$；
• 恰好有一个 A 和一个 B；
• 所有非墙格子构成一棵树。