Fredrik 和 Abdullah 正在进行一场激光象棋对弈。游戏在一个网格上进行，目标是用激光束射击对手的国王。Abdullah 有一个攻击棋子，按下按钮时，它会向四个方向（上、下、左、右）发射激光。攻击棋子在网格上标记为 A。Fredrik 的国王标记为 K。网格上还有标记为 o 的镜子棋子。当激光击中镜子棋子时，光束会向四个方向反射。
游戏目前处于这样一种状态：如果 Abdullah 按下按钮发射激光，他就能获胜。为了阻止 Abdullah 获胜，Fredrik 在棋盘上放置了标记为 R 的烟雾弹。烟雾会阻止激光束穿过该方格。每过一秒，烟雾就会向四个相邻的方格扩散。如果攻击棋子或国王处于烟雾中，Abdullah 就无法获胜。
请问需要多少秒，Abdullah 才能在按下按钮时不再获胜？换句话说，烟雾扩散到什么程度，使得激光无法再从攻击棋子到达国王？题目保证游戏初始状态下，激光可以从攻击棋子到达国王，且路径上没有经过任何烟雾。
输入格式
第一行包含两个整数 $R$ 和 $C$ ($1 \le R, C$ 且 $R \times C \le 40,000$)，表示游戏棋盘的行数和列数。
接下来的 $R$ 行描述了游戏棋盘的布局。第 $i$ 行包含 $C$ 个字符，描述了第 $i$ 行的外观。每个字符为以下之一：
.表示空方格o表示镜子棋子R表示烟雾弹A表示攻击棋子K表示国王
题目保证 A 和 K 各出现恰好一次，R 至少出现一次，且初始时激光能从攻击棋子到达国王。
输出格式
输出烟雾扩散到激光无法到达国王所需的时间（秒数）。
子任务
你的程序将在若干测试组上进行测试。为了获得某一组的分数，必须通过该组中的所有测试用例。
| 组别 | 分值 | 数据范围 |
|---|---|---|
| 1 | 10 | $R = 1$ |
| 2 | 20 | 棋盘上恰好有一个 R |
| 3 | 20 | 没有空方格 (.) |
| 4 | 20 | $R \times C \le 400$ |
| 5 | 30 | 无额外限制 |
样例
输入格式 1
3 3 .Ao R.. .Ko
输出格式 1
2
输入格式 2
5 8 A......o ..K.o... o....o.o ..o..o.. R...o..o
输出格式 2
4
输入格式 3
10 9 oo.o.oRR. .K.oo..R. ....oo..R ..R...... ..R...... A....o.o. ...R..... .....o.o. ......... o....o..R
输出格式 3
3