As the navigator of the newly christened RMS Titanic II, you've been commissioned to plot the ship's course through the ocean, represented by an ~R~ by ~C~ grid. Keeping with the tradition of the biggest and best, the Titanic II is a large ship, with length ~L~ and width ~W~ ~(1 \le L \le R, 1 \le W \le C)~. Not wanting awful newspaper headlines again, you decide that this time, you will do your best to avoid icebergs, which are represented by the character #. The ship can move freely through open ocean, which is represented by the character ..

Since you lost a lot of money in the first Titanic, management decided to make some cuts. Specifically, the Titanic II cannot rotate. This means that if ~L = 5~, ~W = 3~, the ship cannot rotate and have ~L = 3~ and ~W = 5~. The ship can move in all four cardinal directions, but not diagonally in one move.

You are to find the minimum amount of moves it would take to travel between your starting point at ~(0,0)~ (the top-left corner) and the destination ~(C-1, R-1)~ (the bottom-right corner) such that any point on your ship is on ~(C-1, R-1)~. A move consists of moving once up, left, down, or right.

Note that the ship is not guaranteed to start on a valid position, nor end on a valid position.

For this question, Python users are recommended to use PyPy in order to pass the time limit.

Input Specification

The first line will contain the integers ~R~ and ~C~ (space separated), representing the rows (y-axis) and columns (x-axis) of the ocean.

The second line will contain the integers ~L~ and ~W~ (space separated), representing the ship's length (y-axis) and width (x-axis).

The next ~R~ lines will contain ~C~ characters that are either . or #.

It is guaranteed that the ocean will not be smaller than the Titanic II.

Constraints

For all subtasks:

~1 \le L \le R \le 2\,000~

~1 \le W \le C \le 2\,000~

Subtask 1 [30%]

~1 \le L \le R \le 50~

~1 \le W \le C \le 50~

Subtask 2 [70%]

No additional constraints.

Output Specification

Output the minimum amount of moves it would take for the Titanic II to get to its destination. If no such path exists, output -1.

Sample Input 1

5 6
1 2
.....#
..#..#
.#...#
.....#
..#...

Sample Output 1

8

Explanation for Sample Output 1

00...#       .11..#       ..22.#       ...33#       .....#       .....#       .....#       .....#       .....#
..#..#       ..#..#       ..#..#       ..#..#       ..#44#       ..#..#       ..#..#       ..#..#       ..#..#
.#...#       .#...#       .#...#       .#...#       .#...#       .#.55#       .#...#       .#...#       .#...#
.....#       .....#       .....#       .....#       .....#       .....#       ...66#       .....#       .....#
..#...       ..#...       ..#...       ..#...       ..#...       ..#...       ..#...       ..#77.       ..#.88

Remember that the Titanic II cannot turn, so the single fastest route is three steps right, four steps down and one step right (as outlined above). The diagram above shows the spaces that the Titanic II occupies, for every step.

Sample Input 2

2 3
1 2
...
#..

Sample Output 2

2

Explanation for Sample Output 2

00.       .11       ...
#..       #..       #22

The Titanic II can move to the right, then down, for a total of 2 steps. The diagram above shows the spaces that the Titanic II occupies, for every step.

Sample Input 3

5 5
2 2
.....
....#
...#.
.....
..#..

Sample Output 3

-1

Explanation for Sample Output 3

The Titanic II cannot reach the bottom-right corner, as there is no way for a ~2 \times 2~ ship to fit through the icebergs.