小喵觅食

题号：NC245313
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

The__Flash 回到家迫不及待地跟 PLMM 分享买回来的零食，PLMM 拿起一包小鱼干正准备要吃，这时恰巧有一只小喵在觅食，引起了 PLMM 的注意。

现实世界可以抽象为一张 $n \times m$ 大小的二维地图。PLMM 的初始坐标在 $(x_1,y_1)$ ，活动范围 $r_1$ 表示 PLMM 只会移动到坐标为 $(x,y)$ 的位置 $(0 \leq |x-x_1|+|y-y_1| \leq r_1)$ 。小喵的初始坐标在 $(x_2,y_2)$ ，鼻子灵敏度 $r_2$ 表示小喵只能闻到坐标为 $(x,y)$ 的位置的小鱼干 $(0 \leq |x-x_2|+|y-y_2| \leq r_2)$ 。此外，地图中存在若干障碍物使得 PLMM 和小喵无法通过。

若 PLMM 或小喵当前的坐标为 $(x,y)$ ，则下一步可以移动到 $(x-1,y),\,(x,y-1),\,(x+1,y)$ 或 $(x,y+1)$ 坐标的位置。起初，小喵保持原地不动，但当闻到小鱼干的气味时便会朝 PLMM 的位置跑去。在小喵开始移动的同时，PLMM 会担心吓跑小喵从而保持原地不动。需要注意的是，鼻子灵敏度 $r_2$ 只能决定小喵能否闻到小鱼干的气味，对小喵的移动范围没有限制。小喵闻到小鱼干气味后便会锁定 PLMM 的位置，即使之后闻不到小鱼干的位置，也会继续朝 PLMM 的位置移动。

若小喵可以吃到小鱼干，PLMM 想知道自己与小喵移动的距离和最小值。

输入描述:

第一行输入两个整数 。

第二行输入两个整数 。

接下来输入  行，每行输入一个长度为  的字符串  表示二维地图。 表示地图坐标为  的位置，其中  表示 PLMM 的初始位置， 表示小喵的初始位置， 表示障碍物不允许通过， 表示空地允许通过。

保证地图中字符  有且仅有一个，字符  有且仅有一个。

输出描述:

若小喵可以吃到小鱼干则输出 PLMM 与小喵移动的距离和最小值，否则输出 。

示例1

输入

复制

5 3
2 1
...
.M.
...
...
.P.

输出

复制

说明

PLMM 进行移动 ，此时小喵闻到了坐标  位置上小鱼干的气味并进行移动 。

示例2

输入

复制

5 3
1 2
**.
*M.
**.
*..
*P.

输出

复制

说明

PLMM 进行移动  ，此时小喵闻到了坐标  位置上小鱼干的气味并进行移动 。

示例3

输入

复制

5 3
2 1
**.
*M.
**.
*..
*P.

输出

复制

-1

说明

PLMM 从初始位置  出发，在至多走  步的条件下无论怎样都无法让小喵闻到小鱼干的气味，所以小喵无法吃到小鱼干。