Public Transport

Task

After solving the black hole equations, Giorgio has patented a brand-new project for a teleport machine. This handy device would approximately resemble a photo booth, and allow customers to be instantly dematerialized and then fully reassembled into a perfectly functional human being, in another teleport machine of their choice. Since there are no known side effects as of now, Giorgio is enthusiastic about his new project and cannot wait to realize it. However, building a teleport machine is pretty expensive (and definitely out of his budget): so it is time to get a sponsor!

Giorgio laid out a map of the city of Torino, consisting of streets, buildings and the proposed teleport machines. This map is a grid of $H \times W$ characters $C_{ij}$, which can be either:

• . to represent a street, square or any other open space in the city;
• # to represent a building, river or any other obstacles;
• @ to represent a teleport machine;
• C to represent the city hall;
• M to represent the mayor's house.

A citizen can freely move from a block to any adjacent block in any of the four directions N - E - W - S, unless the destination block contains an obstacle \#. This operation takes $1$ minute. If he is in a block containing a teleport machine, he can also use it to move to any other teleport machine in $1$ minute (This is the time needed for paying a small fee and selecting the correct destination: the teleport itself is instantaneous).

In order to persuade Chiara the city mayor to fund his project, it is crucial to calculate the time needed to go from the city hall to the mayor's house. In this way, he can show her how much it would be shortened by the teleport machines.

Input data

The first line contains the two integers $H$ and $W$. Other $H$ lines follow, each containing a string consisting of $W$ characters among ., #, @, C, M.

Output data

You need to write a single line with an integer: the duration in minutes of the fastest trip from the city hall to the mayor's house, possibly using the teleport machines.

Constraints and clarifications

• $1 \le H,W \le 1000$.
• $C_{i,j}$ is a character among ., #, @, C, M.
• There is exactly one city hall and one mayor's house.
• There is always a path reaching the mayor's house starting from the city hall.

Example 1

stdin

5 4
@..#
##..
C..M
.#.#
.#@.

stdout

3

Explanation

In the first sample case, it is not convenient to use the teleport machines.

Example 2

stdin

6 10
#@.......@
#.###..@##
C.###.####
#@###.####
#......@#M
@.#####...

stdout

7

Explanation

In the second sample case, the best path is the following: