There will be exactly one S character and at least one . character. The first and last character of every row and column will be W .

For \(5\) of the \(15\) marks available, there are no cameras or conveyors.

For an additional \(5\) of the \(15\) marks available, there are no conveyors.

Output Specification

For each empty cell, print one line with one integer, the minimum number of steps for the robot to move to this empty cell without being caught or -1 if it is impossible to move to this empty cell.

The output should be in row major order; the order of empty cells seen if the input is scanned line by line top-to-bottom and then left-to-right on each line. See the sample outputs for examples of row major order output.

Sample Input 1

4 5
WWWWW
W.W.W
WWS.W
WWWWW

Sample Output 1

-1
2
1

Explanation for Sample Output 1

The robot cannot move to the top left empty cell because it is blocked by walls.

The top right empty cell can be reached in \(2\) steps and the bottom right empty cell can be reached in \(1\) step.

Sample Input 2

5 7
WWWWWWW
WD.L.RW
W.WCU.W
WWW.S.W
WWWWWWW

Sample Output 2

2
1
3
-1
-1
1

Explanation for Sample Output 2

The empty cell to the immediate left of the robot is seen by the camera so the robot cannot move there.

The empty cell right below the R conveyor is also seen by the camera as conveyors do not block the sight of cameras.

Note that the robot can use the U and L conveyors to avoid getting caught by the camera.

If the robot moves to the R conveyor, it will become stuck there forever.