小泽来到一座带有传送滑道的迷宫。迷宫由 $N$ 行 $M$ 列的网格组成，四周除一个出口外都被障碍封住。每个格子可能是障碍、普通道路、传送滑道的端点或出口。

小泽每次可以走到上、下、左、右相邻且不是障碍的格子，走一步需要 $1$ 个单位时间。每条传送滑道有两个端点，用同一个大写英文字母表示；一旦走到某个端点，就必须立刻被传送到另一个端点，传送本身不花费时间，两个方向都可以使用。

地图中的字符含义如下：

• # 表示不能通过的障碍；
• . 表示普通道路；
• A～Z 表示传送滑道端点，同一个字母恰好出现两次；
• = 表示出口；
• @ 表示小泽当前所在的普通道路格。

请计算小泽从 @ 出发到达出口所需的最短时间。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $M$。

接下来 $N$ 行，每行包含 $M$ 个字符，描述迷宫。字符之间没有空格。

输出格式

输出一个整数，表示小泽到达出口所需的最短时间。

5 6
###=##
#.W.##
#.####
#.@W##
######

3

18 22
@.....................
....#.#........#...#..
....#...........#.....
......#.####......#...
.....#.#.#...#........
........#.....#.#.....
......#.#..#.....#....
.#...#.......#....#...
#............#........
#....#............#...
#.#.......#...........
....#..##......#.#....
.#.......#...#.#......
......#.#.....##....#.
.....#.....#.#.#..##..
.......#.#............
#................#.#..
#...#..##...##.......=

38

21 5
@....
.....
.....
..##.
...#.
.....
.....
..#..
#....
...#.
.....
.#.#.
...#.
.#.#.
#..#.
.....
#....
..#..
.....
..#..
....=

24

样例说明

样例中只有一条用字母 W 标记的传送滑道。小泽先向右走到滑道端点，花费 $1$ 个单位时间；随后立即传送到另一个 W，不花费时间；再向右、向上各走一步到达出口，因此总时间为 $3$。

数据范围与约定

$2\le N,M\le 300$。