JOI-kun enjoys ice skating on a vast, natural skating rink.
The skating rink is a rectangle consisting of $R$ rows and $C$ columns. We denote the cell at the $r$-th row from the north and $c$-th column from the west as cell $(r, c)$. Each cell is either a cell that JOI-kun can pass through, or a cell that is impassable due to an ice block. Furthermore, all cells on the perimeter of the skating rink have ice blocks, so he will never go outside the rink. That is, cells $(i, 1)$, $(i, C)$ for $1 \le i \le R$, and cells $(1, j)$, $(R, j)$ for $1 \le j \le C$ contain ice blocks.
JOI-kun is not very good at skating. When moving on the skating rink, he kicks off from his current cell in one of the four cardinal directions (north, south, east, or west) and slides until he stops at the cell just before hitting an ice block. One kick followed by stopping is counted as one move. If there is an ice block in an adjacent cell in a chosen direction, he cannot move in that direction.
One day, while JOI-kun was enjoying skating, he noticed that whenever he kicks off from a cell, an ice block grows on that cell. Ice blocks do not grow on cells he passes through, except for the cell he kicked off from. Since it is very dangerous to continue skating in this state, JOI-kun wants to escape from this skating rink as quickly as possible.
JOI-kun's current location is cell $(r_1, c_1)$. To escape from this skating rink, he needs to stop at the exit cell $(r_2, c_2)$. Write a program to calculate the minimum number of moves required for JOI-kun to start moving from his current location and stop at the exit cell so that he can escape the skating rink safely. Depending on the state of the skating rink and JOI-kun's current location, it might be impossible for him to stop at the exit cell no matter how he moves. Note that simply passing through the exit cell during a move does not count as escaping the skating rink; he must stop there.
Task
Given the information about the ice blocks on the skating rink, JOI-kun's current location, and the position of the exit cell, determine whether JOI-kun can start from his current location and stop at the exit cell. If he can, find the minimum number of moves required.
Input
Read the following data from standard input:
- The first line contains two space-separated integers $R$ and $C$, representing the size of the skating rink as $R$ rows and $C$ columns.
- The next $R$ lines each contain a string of length $C$. Each character is either '.' or '#'. The $c$-th character of the $r$-th line ($1 \le r \le R, 1 \le c \le C$) represents the initial state of cell $(r, c)$. If the character is '.', the cell is passable; if it is '#', the cell contains an ice block and is impassable.
- The next line contains two space-separated integers $r_1$ and $c_1$, representing JOI-kun's current location $(r_1, c_1)$.
- The next line contains two space-separated integers $r_2$ and $c_2$, representing the exit cell $(r_2, c_2)$.
Output
Output the minimum number of moves required for JOI-kun to start from his current location and stop at the exit cell as an integer on a single line. If it is impossible for JOI-kun to stop at the exit cell, output -1.
Constraints
All input data satisfies the following conditions:
- $3 \le R \le 1000$
- $3 \le C \le 1000$
- $1 \le r_1 \le R$
- $1 \le c_1 \le C$
- $1 \le r_2 \le R$
- $1 \le c_2 \le C$
- All cells on the perimeter of the skating rink contain ice blocks. That is, cells $(i, 1)$, $(i, C)$ for $1 \le i \le R$, and cells $(1, j)$, $(R, j)$ for $1 \le j \le C$ contain ice blocks.
- Cells $(r_1, c_1)$ and $(r_2, c_2)$ do not contain ice blocks.
Subtasks
Subtask 1 [13 points]
The following conditions are satisfied:
- $R \le 10$
- $C \le 10$
- If JOI-kun can start from his current location and stop at the exit cell, the required number of moves is at most 10.
Subtask 2 [65 points]
The following conditions are satisfied:
- $R \le 200$
- $C \le 200$
Subtask 3 [22 points]
There are no additional constraints.
Examples
Input 1
5 5 ##### #...# #...# #...# ##### 2 2 3 3
Output 1
4
Note 1
In Example 1, the initial state of the skating rink is as follows. Cells with white squares contain ice blocks, 'J' represents JOI-kun's current location, and 'E' represents the exit.
First, if JOI-kun moves east, the state of the skating rink becomes:
After this, by moving west, south, and north in order, he can stop at the exit in a total of 4 moves. Since it is impossible to stop at the exit in 3 or fewer moves, output 4.
Input 2
8 6 ###### #..#.# ##...# #....# #.#..# #....# ##...# ###### 4 3 6 4
Output 2
5
Input 3
5 5 ##### #.#.# #.#.# #.#.# ##### 2 2 4 4
Output 3
-1
Input 4
3 3 ### #.# ### 2 2 2 2
Output 4
0
Note 4
In Example 4, since JOI-kun's current location is the exit cell, the required number of moves is 0.