### 问题描述 桥田君正在玩一款叫作《吃豆人》的游戏，游戏的玩法是这样的，在一个 $N \times M$ 的网格中有 $4$ 种不同的游戏单位，分别是障碍物、吃豆人、豆子和幽灵。其中吃豆人可以花一单位时间朝上下左右四个方向走一单位长度，当它走到有豆子的网格时，它便能吃掉网格里的豆子，且豆子不可再生，但它不能走到有障碍物或者幽灵的网格中。而幽灵只能花一单位时间朝规定的方向走一单位长度，同样，它也不能走到有障碍物的网格中，但它经过有豆子的网格时并不会吃掉网格里的豆子。注意，幽灵会在碰到障碍物后反方向移动，并保持当前方向直到又碰上障碍物。现在网格里有多个吃豆人和一个幽灵（至少一个吃豆人），桥田君想知道，对于任意一个豆子，这些吃豆人最少得花多少时间才能将它吃掉，并且不碰上幽灵，你能帮助他解决这个问题吗？请输出所有将任意一颗豆子吃掉所需的最少时间中的最大值。 ### 输入格式 第一行三个正整数 $N,M,K$，表示有 $N$ 排 $M$ 列个网格，$K$ 表示幽灵规定的初始移动方向，$0$ 代表向上走，$1$ 代表向右走。 接下来 $N$ 行，每行 $M$ 个字符，可能是 `#`、$B$、$P$ 或者 $G$ 这四种字符中的一种，分别代表第 $i$ 排第 $j$ 列的网格里是障碍物、豆子、吃豆人和幽灵。 ### 输出格式 输出共一行，输出一个整数表示所有将任意一颗豆子吃掉所需的最少时间中的最大值。数据保证网格里的任意一颗豆子一定能被吃豆人吃掉。 ### 样例输入 ```text 6 6 0 ###### ##BPB# ##B#G# #PBBB# #B#### ###### ``` ### 样例输出 ```text 5 ``` ### 说明 样例中，位于 $(2,3)$、$(4,3)$ 和 $(5,2)$ 网格中的豆子最少只要花费 $1$ 单位时间就能被吃掉；位于 $(3,3)$ 和 $(4,4)$ 网格中的豆子最少只要花费 $2$ 单位时间就能被吃掉；位于 $(2,5)$ 网格中的豆子因为幽灵的存在最少需花费 $3$ 单位时间才能被吃掉，因为在第 $1$ 单位时间时，幽灵在网格 $(2,5)$ 处；位于 $(4,5)$ 网格中的豆子因为幽灵的存在最少需花费 $5$ 单位时间才能被吃掉，因为在第 $3$ 单位时间时，幽灵在网格 $(4,5)$ 处。所以答案为 $3$。 ### 评测数据规模 对于所有评测数据，$5 \leq N,M \leq 100$，$0 \leq K \leq 1$。