题目描述

小明参加了一座花园迷宫闯关活动。这座迷宫不只是普通的通道迷宫——它设置了若干条双向传送门通道，每条传送门连接两个指定格子，踏入任意一端都会被瞬间传送到另一端，耗时为零。

迷宫外围由不可通行的围墙（用 # 表示）完全包围，仅有一个出口（用 = 表示）。迷宫用 $N \times M$（$2 \le N \le 300$，$2 \le M \le 300$）的网格表示。每个格子为以下四种之一：

• 墙壁（#）：不可通行
• 空地（.）：可以通行
• 传送门端点（大写字母 $\texttt{A}$ ~ $\texttt{Z}$）：每对相同字母标记一条传送门的两端，不同传送门使用不同字母
• 出口（=）

小明站在一个空地格子上，用 @ 标记。每次移动只能走到相邻（上下左右）的格子，且目标不能是墙壁。从空地走到相邻空地耗时 $1$ 个单位，从传送门一端传送到另一端耗时 $0$ 个单位。如果小明踏入一个传送门端点，必须立即被传送。

求小明从起点 @ 到达出口 = 所需的最少时间。

输入格式

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

接下来 $N$ 行，每行 $M$ 个连续字符，描述迷宫的第 $i$ 行。

输出格式

一个整数，表示小明到达出口的最少时间。

样例

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

3

提示

样例解释：

###=##
#.W.##
#.####
#.@W##
######

唯一的传送门端点用字母 W 标记。最优路径（耗时 $3$）：右移 $1$ 步到传送门端点 $\to$ 传送到另一端（耗时 $0$）$\to$ 右移 $1$ 步 $\to$ 上移 $1$ 步到出口。