Stepan develops an electronic circuit on a rectangular grid of size n * m. There are n * m square tiles in total. Two (out of four) opposite corners of each tile are connected by a wire.

The power supply is connected to the upper left corner of the grid, the lamp is connected to to the lower right corner. In order to turn on the lamp, you can turn any tile 90 degrees in both directions.

In the image, the lamp is off. If you turn any tile in the second column from the right, the lamp will turn on.

Write a program that will find the minimum number of tiles that must be turned over to turn on the lamp.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 500) - the size of the grid. It is followed by n lines of m characters each - \ or /, characterizing the direction of the wire on this tile.

Output

Print the answer to the problem, or the message "NO SOLUTION" if it is impossible to turn on the lamp.