Color Tokens (PY)

A new robot is being tested in FEL Labs.
There is a training grid consisting of squares. Some squares contain color tokens. There are three types of tokens - red green and blue. Each square contains at most one token. At the start of the testing, the robot stands on one square in the grid which is free of tokens.
In one step, the robot can move from its current square to any of the immediately adjacent squares in the North, South, West or East directions, provided that those squares do exist. The robot cannot move outside the grid.
The task of the robot is to move around the grid, collect some tokens and return back to the start square. Any particular token can be collected only when the robot stands on the square where the token is located. The robot has to collect at least one token of each color.

   

Image 1. Grids a), b), c) corresponding to Examples 1, 2, 3 below. The robot start position is marked by a crossed square. The tokens are drawn as color circles. The possible shortest robot paths (= sequences of steps) are marked by a dotted line. Note that there might be more paths consisting of the same number of steps which solve the problem.  

The task

Find the minimum number of steps the robot has to perform to collect at least one token of each color and return to the start position.


Input

The first input line contains two integers M, N, separated by space. The values M and N indicate (in this order) the number of rows and the number of columns in the grid.
Next, there are M text lines representing the grid. Each line represents one row of the grid and it contains a string consisting of exactly N characters. Each character represents the contents of the corresponding square in the grid. The only possible characters are

There is always exactly one character "X" in the whole grid and at least one character representing each color.
It holds 3 ≤ M, N ≤ 1000, the number of tokens of each color in the grid does not exceed 100.

Output

The output contains one text line with one integer representing minimum number of steps the robot has to perform to collect at least one token of each color and return back to the start position.

Example 1

Input
3 3
G.B
.X.
R..
Output
8
The grid presented in Example 1 is depicted in Image 1a).

Example 2

Input
6 5
.GGRG
.....
.X...
.....
B...R
B.RRR
Output
14
The grid presented in Example 2 is depicted in Image 1b).

Example 3

Input
11 15
X......R.......
...............
...............
...............
.......G......B
...............
...............
...............
...............
...............
R.G.B..........
Output
28
The grid presented in Example 3 is depicted in Image 1c).

Public data

The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set