Description

In a flash, a huge matrix of $H$ rows and $W$ columns appears on the ground. Each cell is either empty land . or an obstacle #.

They start at $(1, 1)$ and must escape to the exit at $(H, W)$. They can move one cell up, down, left, or right; each such move counts as one operation. They still have the magic potion from their last adventure. If they drink it in one go, they can instantly teleport by the relative vector $(D, R)$; that is, if their current position is $(x, y)$, the new position becomes $(x + D, y + R)$. This also counts as one operation, but they can use this operation at most once (they may also choose not to drink the potion).

This is a dangerous place. They want to know the minimum number of operations needed to get out. However, it might be impossible to escape; in that case, they can only await their fate.

Input Format

The first line contains four integers $H$, $W$, $D$, $R$, whose meanings are explained in the description.

The next $H$ lines each contain a string of length $W$, consisting only of . and #.

Output Format

Output a single integer representing the minimum number of operations needed to escape. If they cannot escape, output $-1$.

3 6 2 1
...#..
..##..
..#...

5

3 7 2 1
..#..#.
.##.##.
.#..#..

-1

6 6 -2 0
.#....
.#.#..
.####.
.#..#.
.##.#.
....#.

21

Hint

Sample explanation 1.

$(1, 1) \to (1, 2) \to (1, 3) \to$ drink the magic potion $\to (3, 4) \to (3, 5) \to (3, 6)$.

Sample explanation 2.

Since there is only one bottle of magic potion, they cannot escape.

Sample explanation 3.

$D$ and $R$ can also be $0$ or negative.

Constraints and Notes.

• For $40\%$ of the testdata, $2 \le H, W \le 5$.
• For $70\%$ of the testdata, $2 \le H, W \le 100$.
• For $100\%$ of the testdata, $2 \le H, W \le 1000$, $|D| < H$, $|R| < W$.

Translated by ChatGPT 5