题目描述

今年秋天，约翰带着奶牛们去玩玉米迷宫。迷宫可分成$\red{N\times M}$个格子，有些格子种了玉 米，种宥玉米的格子无法通行。

迷宫的四条边界上都是种了玉米的格子，其屮只有一个格子没种，那就是出口。

在这个迷宫里，有一些神奇的传送点$\red{6}$每个传送点由一对点组成，一旦 走入传送点的某个结点，机器就会强制把你送到传送点的另一头去。所有的传送点都是双向 的，如果你定到了另一头，机器也会把你送回来。

奶牛在一个单位的时间内只能向相邻的四个方向移动一格，不过传送机传送是瞬间完成的。

现在$\red{W}$西在迷宫里迷路了，她只知道目前的位罝在哪里，请你帮助她用最短的时间走出 迷宫吧。

输入格式

第一行：两个用空格分开的整数：$\red{N}$和$\red{M,2}$

第二行到$\red{N+1}$行：第$\red{i+1}$行有$\red{M}$个连续的字符，描述了迷宫第$\red{i}$行的信息。其中"$\red{\#}$"代 表不能通行的玉米地，

"$\red{.}$"代表可以通行的草地，"$\red{@}$"代表贝西的起始位罝，"$\red{=}$"代表迷宫出口，

大写字母"$\red{A}$"到"$\red{Z}$"总是成对出现的，代表一对传送点

输出格式

第一行：一个整数，表示贝西走出迷宫的最短时间，保证逃离迷宮的路线一定存在

样例

输入样例

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

######

输出样例

3

提示

从起点向右走，通过$\red{w}$传送，再从另一端 走出迷宫