You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

世界将要陷入无尽黑暗，身为不死人的你需要将那些不愿意传火的薪王干掉。 在路上会遇到许多困难，你需要找一条最快的路来到薪王的所在地。

Description

1.'S'表示起点
2.'#'表示墙壁
3.'.'表示可以通过的路
4.'@'表示篝火（篝火之间可以相互传送，且篝火数量不为 1 ）
5.'P'表示薪王房间
不死人能在一格地点上可能存在的四个相邻的格子移动，花费 1 个单位时间。篝火之间的传送不花费时间。
PS：传送不一定利于赶路

Format

Input

第 1 行：一个 N × M的地图（3<=N<=200,3<=M<=200）
第 2 行到第 N+1 行：每行 M 个字符，它们表示网格图中的一排。字符之间没有空格。

Output

输出最快的路线需要的时间
如果到不了输出 -1

Samples

4 4
S.@.
.#..
..##
@P##

3

4 4
#S#.
.#..
....
...P

-1

Limitation

1s, 1024KiB for each test case.