Escape the Haunted Matrix

You are given a matrix of size $H \times W$ consisting of characters either . (empty cell) or # (obstacle). You start at the top-left cell $(1,1)$ and need to reach the bottom-right cell $(H,W)$.

You can move one step at a time in one of the four cardinal directions (up, down, left, right). In addition, you have a single-use magic potion which allows you to teleport exactly once. When you use the potion at cell $(x,y)$, you instantly move to the cell $(x+D,\,y+R)$. Both a normal move and the teleport move each count as one step. It is allowed not to use the teleport move at all.

Your task is to determine the minimum number of steps required to reach the destination. If it is impossible to escape, print -1.

inputFormat

The first line contains four integers $H$, $W$, $D$, $R$, where $H$ and $W$ denote the number of rows and columns of the matrix, and $D$, $R$ denote the row and column offset for the teleport move.

This is followed by $H$ lines, each containing a string of length $W$. Each character is either . (empty cell) or # (obstacle).

outputFormat

Print a single integer representing the minimum number of steps required to reach from $(1,1)$ to $(H,W)$. If it is impossible to reach the destination, print -1.

sample

3 3 1 1
...
.#.
...

4