Problem Background

Refer to the previous adventure at https://www.luogu.com.cn/problem/P1373.

Little a and uim find themselves once again in the rainforest. Suddenly, a strong southern wind brings a dark cloud rushing from the south, accompanied by flashes of lightning and thunder. In an instant, the wind picks up, and the sky is covered with dark clouds. Large raindrops start falling from the sky, and a minotaur-like monster appears in front of them, speaking in a low voice: "Hehe, since you've come here, neither of you will leave alive!" Little a and his companion are once again stunned!

Problem Description

Instantly, a giant matrix of $H$ rows and $W$ columns appears on the ground, with each cell either being an open space . or an obstacle #.

Their starting point is at $(1,1)$, and they need to escape to the exit at $(H,W)$. They can move one cell up, down, left, or right in one step. However, they still have the magic liquid collected from their previous adventure, which allows them to teleport to a position $(D,R)$ relative to their current position; that is, if their current position is $(x,y)$, they can move to $(x+D,y+R)$ in one step. They can only use this ability at most once (or not at all).

This place is a dangerous one. Therefore, they want to know the minimum number of steps required to escape this perilous place. However, they might not be able to escape, in which case they can only wait for their fate.

Input Format

The first line contains four integers, $H, W, D, R$, as described in the problem.

The next $H$ lines, each of length $W$, consist of only . or # characters.

Output Format

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

Sample Input and Output

Sample Input #1

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

Sample Output #1

5

Sample Input #2

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

Sample Output #2

-1

Sample Input #3

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

Sample Output #3

21

Notes

Sample Explanation #1

$(1,1) \to (1,2) \to (1,3) \to$ use magic liquid $\to (3,4) \to (3,5) \to (3,6)$.

Sample Explanation #2

Since they only have one dose of magic liquid, they cannot escape.

Sample Explanation #3

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

Data Range and Constraints

$40\%$ of the test cases have $2 \leq H, W \leq 5$.

$70\%$ of the test cases have $2 \leq H, W \leq 100$.

$100\%$ of the test cases have $2 \leq H, W \leq 1000, |D| < H, |R| < W$.

见题面 Input 部分

见题面 Output 部分