Bessie's Knightly Lilypad Journey

Farmer John has built a beautiful rectangular pond partitioned into M rows and N columns. Each cell in the grid represents either a cell with an already existing lilypad, a cell with a rock, or a cell filled with water. Bessie, currently standing on a lilypad, wants to jump like a chess knight from one lilypad to another to reach her destination lilypad. Her knight‐move jump consists of moving two cells in one direction (horizontal or vertical) and then one in the perpendicular direction.

However, sometimes the intermediate lilypad needed for her jump is missing. Farmer John can place additional lilypads on any water cell (cells marked with '.') to help her complete her journey. Note that lilypads cannot be placed on cells with rocks (cells marked with 'R'). Cells that already have a lilypad (marked with 'S', 'D' or 'L') are available and require no additional placement.

Your task is to determine the minimum number of additional lilypads that must be placed in order for Bessie to move from her starting lilypad to the destination lilypad using knight moves and to count in how many distinct ways these additional pads can be placed to achieve that minimum.

Note on cell representations:

• S : Starting lilypad (Bessie's initial position)
• D : Destination lilypad
• L : Already existing lilypad
• . : Water cell (a new lilypad can be placed here at a cost of 1)
• R : Rock (blocked, cannot place a lilypad)

The knight moves are defined by the following offsets in rows and columns: \(\{(2,1), (2,-1), (-2,1), (-2,-1), (1,2), (1,-2), (-1,2), (-1,-2)\}\). When Bessie jumps, if the landing cell is water, an extra lilypad must be placed (cost 1) to make that jump possible; if the landing cell already has a lilypad, no extra cost is incurred.

inputFormat

The first line contains two integers M and N (1 ≤ M, N ≤ 30), representing the number of rows and columns of the pond.

The next M lines each contain a string of N characters. Each character is one of the following:

• S: Starting lilypad (exactly one in the grid)
• D: Destination lilypad (exactly one in the grid)
• L: An existing lilypad
• .: A water cell (where you may place a new lilypad at a cost of 1)
• R: A rock (cannot be used or replaced)

It is guaranteed that there is at least one solution if additional lilypads are placed appropriately.

outputFormat

Output two space‐separated integers on a single line. The first integer is the minimum number of additional lilypads that must be placed so that Bessie can travel from the starting lilypad to the destination lilypad using knight moves. The second integer is the number of distinct ways to place that minimum number of additional lilypads.

If it is impossible to reach the destination, output "-1 0".

sample

3 3
S..
..D
...

0 1