Description

It's a game played on a specific board about navigation.

Here are the rules: You can start voyage from any harbor chosen by yourself in the south (the bottom row), and the goal is to reach any harbor in the north (the top row) in shortest time.

Your boat may go north (upward), west (leftward) or east (rightward), just one grid each time, but it cannot navigate to rush to the grid of land or obstacles. In addition, it is considered useless (although sometimes not really) to go backward. So once you leave a grid, you cannot return to it.

It takes only one unit of time to go north, while the time spent on a horizontal (going west/east) movement depends on the number of continuous horizontal movements before this movement. It means that if X continuous horizontal movements have been done just before this movement, the amount of the units of time spent by the next horizontal movement is X + 1.

In the sea, there are some kinds of special objects.

• Obstacles. You cannot move into these grids.
• Fortune's wheels. In this game, Fortune's wheels really look like a weird wheel. You must meet Fortune's wheel ODD TIMES.
• Blessing stones. It costs NO time to go to this kind of grids.
• Invocations of storm. It costs DOUBLE time as normal to go to this kind of grids.

Input

There are two integers N and M in the first line. It is guaranteed that both N and M do not exceed 1000. N lines follows, and each line contains M characters describing the grid:

- In first and N-th of there N lines, 'H' stands for harbor, '.' stands for land. - In other lines, '.', 'O','F','B' and 'S' stand for Empty grids, Obstacles, Fortune's wheels, Blessing stones and Invocations of storm respectively.

Output

If a solution exists, output an integer, which is the minimum time required; otherwise, output "No solution".

5 11
...H...H...
.O.BF.FS.O.
O.O.OOO.O.O
.O...F...O.
.....H.....

6

Source

POJ Monthly--2006.06.25

, Yang Yi