Teleportation Maze Adventure

Farmer John recently took his cows to a corn maze that features gravity‐powered teleporter slides. The maze is represented as an \(N \times M\) grid (with \(2 \le N, M \le 300\)). Each cell in the grid is one of the following:

• Corn represented by # (impassable)
• Grass represented by . (passable)
• Slide endpoint represented by an uppercase letter (A–Z). Each letter appears exactly twice. If a cow moves onto a slide endpoint, she is immediately teleported to the other endpoint of that slide. This teleporter slide is bidirectional and costs \(0\) time units.
• Exit represented by =

Bessie is lost in the maze. Her starting position is on a grassy cell denoted by @. From any grassy cell, she can move to a horizontally or vertically adjacent cell (provided that cell is not corn) at a cost of \(1\) time unit per move. However, if the adjacent cell is a slide endpoint, then upon entering it (which costs \(1\) time unit) she is immediately teleported to the paired endpoint at no extra cost. Note that after being teleported, she is allowed to move normally from the destination cell.

Your task is to determine the minimum time needed for Bessie to reach the exit.

Note: The movement cost is given as follows: stepping from one cell to an adjacent cell costs \(1\) unit of time, and using a teleporter slide costs \(0\) additional time after stepping onto the slide.

inputFormat

The first line of input contains two integers \(N\) and \(M\) (the number of rows and columns of the grid).

The following \(N\) lines each contain a string of length \(M\) describing the maze. The maze is guaranteed to include exactly one starting position (@) and one exit (=). Each teleporter slide is represented by a unique uppercase letter that appears exactly twice in the grid.

outputFormat

Output a single integer representing the minimum time required for Bessie to reach the exit.

sample

3 4
@.A.
##A#
.=..

4