Bessie’s Ballet Jump

Bessie wants to practice her ballet by jumping across a rectangular pond. The pond is divided into M rows and N columns (1 \(\le\) M, N \(\le\) 30). Some cells contain resilient lily pads, some contain rocks, and the rest are filled with water.

Bessie starts on a lily pad marked with S and aims to reach a destination lily pad marked with D. She can only jump from one lily pad to another (cells with characters S, D, or L). She cannot land on water ('.') or rocks ('R').

The jump resembles a knight's move in chess, but with custom distances: in one move Bessie must jump by moving \(M_1\) cells in one direction and \(M_2\) cells in the perpendicular direction, where 1 \(\le\) \(M_1, M_2\) \(\le\) 30 and \(M_1 \neq M_2\). In other words, from cell \((x, y)\) she can move to \((x \pm M_1, y \pm M_2)\) or \((x \pm M_2, y \pm M_1)\).

Your task is to determine the minimum number of moves required for Bessie to reach her destination. It is guaranteed that the destination is reachable.

inputFormat

The first line contains four integers: M, N, M₁, M₂ — the number of rows, the number of columns, and the two jump distances respectively.

This is followed by M lines, each containing a string of length N representing the pond layout. The characters in the grid can be:

• S: the starting lily pad
• D: the destination lily pad
• L: a lily pad
• R: a rock
• '.': water

outputFormat

Output a single integer representing the minimum number of moves Bessie must make to reach the destination.

sample

3 3 1 2
SLL
LRD
LLL

1